2015/04/27 by Friedrich Eisenbrand, Shay Moran, Eisenbrand, Friedrich +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Bipartite graph #Combinatorics #Complexity and Algorithms in Graphs #Computational complexity theory #Computer science #Discrete Mathematics (cs.DM) #Discrete mathematics #Enhanced Data Rates for GSM Evolution #FOS: Computer and information sciences #Graph #Matching (statistics) #Mathematics #Optimization and Search Problems #Time complexity #cs.DM
paper · pdf · doi:10.48550/arxiv.1504.06919
10 pages
openalex publication_date 2015/04/27 · arxiv created 2015/07/02 · arxiv updated 2015/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Suppose you are given a graph G=(V,E) with a weight assignment w:V→ℤ and that your objective is to modify w using legal steps such that all vertices will have the same weight, where in each legal step you are allowed to choose an edge and increment the weights of its end points by 1. In this paper we study several variants of this problem for graphs and hypergraphs. On the combinatorial side we show connections with fundamental results from matching theory such as Hall's Theorem and Tutte's Theorem. On the algorithmic side we study the computational complexity of associated decision problems. Our main results are a characterization of the graphs for which any initial assignment can be balanced by edge-increments and a strongly polynomial-time algorithm that computes a balancing sequence of increments if one exists.