Flow-cut gaps for integer and fractional multiflows

Consider a routing problem instance consisting of a demand graph H = (V, E(H)) and a supply graph G = (V, E(G)). If the pair obeys the cut condition, then the flow-cut gap for this instance is the minimum value C such that there exists a feasible multiflow for H if each edge of G is given capacity C. It is well-known that the flow-cut gap may be greater than 1 even in the case where G is the (series-parallel) graph K_2,3. In this paper we are primarily interested in the "integer" flow-cut gap. What is the minimum value C such that there exists a feasible integer valued multiflow for H if each edge of G is given capacity C? We formulate a conjecture that states that the integer flow-cut gap is quantitatively related to the fractional flow-cut gap. In particular this strengthens the well-known conjecture that the flow-cut gap in planar and minor-free graphs is O(1) [12] to suggest that the integer flow-cut gap is O(1). We give several technical tools and results on non-trivial special classes of graphs to give evidence for the conjecture and further explore the "primal" method for understanding flow-cut gaps; this is in contrast to and orthogonal to the highly successful metric embeddings approach. Our results include the following: • Let G be obtained by series-parallel operations starting from an edge st, and consider orienting all edges in G in the direction from s to t. A demand is compliant if its endpoints are joined by a directed path in the resulting oriented graph. We show that if the cut condition holds for a compliant instance and G + H is Eulerian, then an integral routing of H exists. This result includes, as a special case, routing on a ring, but is not a special case of the Okamura-Seymour theorem. • Using the above result, we show that the integer flow-cut gap in series-parallel graphs is 5. • The integer flow-cut gap in k-Outerplanar graphs is c ^O(k) for some fixed constant c. • A simple proof that the flow-cut gap is O(log k*) where k* is the size of a node-cover in H; this was previously shown by Günlük via a more intricate proof [11].