When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks

Details When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks

2012-03-19

arxiv.org/abs/1203.4041v1

Computer Science

Discrete Mathematics

An extended abstract of this paper will be published at the 44th Symposium on Theory of Computing (STOC 2012)

Scientific paper

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 \emph{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 \emph{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 \emph{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 $K_{2,p}$, with $p\geq 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 \emph{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.

Affiliated with

Also associated with

No associations

Rating

When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-212076