2012/03/19 by Amit Chakrabarti, Chakrabarti, Amit, Lisa Fleischer +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #Interconnection Networks and Systems #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1203.4041
An extended abstract of this paper will be published at the 44th Symposium on Theory of Computing (STOC 2012)
arxiv created 2012/03/19 · openalex publication_date 2012/03/19 · arxiv updated 2012/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G=(V,E) be a supply graph and H=(V,F) a demand graph defined on the same set of vertices. An assignment of capacities to the edges of G and demands to the edges of H is said to satisfy the cut condition if for any cut in the graph, the total demand crossing the cut is no more than the total capacity crossing it. The pair (G,H) is called cut-sufficient if for any assignment of capacities and demands that satisfy the cut condition, there is a multiflow routing the demands defined on H within the network with capacities defined on G. We prove a previous conjecture, which states that when the supply graph G is series-parallel, the pair (G,H) is cut-sufficient if and only if (G,H) does not contain an odd spindle as a minor; that is, if it is impossible to contract edges of G and delete edges of G and H so that G becomes the complete bipartite graph K2,p, with p≥ 3 odd, and H is composed of a cycle connecting the p vertices of degree 2, and an edge connecting the two vertices of degree p. We further prove that if the instance is Eulerian --- that is, the demands and capacities are integers and the total of demands and capacities incident to each vertex is even --- then the multiflow problem has an integral solution. We provide a polynomial-time algorithm to find an integral solution in this case. In order to prove these results, we formulate properties of tight cuts (cuts for which the cut condition inequality is tight) in cut-sufficient pairs. We believe these properties might be useful in extending our results to planar graphs.