All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs

We study the following all-or-nothing multicommodity flow problem in planar graphs. Input: A graph G with n vertices and k pairs of vertices (s₁, t₁), (s₂, t₂),..., (s_k, t_k) in G. Find: A largest subset W of {1, ...., k such that for every i in W, we can send one unit of flow between s_i and t_i. This problem is different from the well-known maximum edge-disjoint paths problem in that we do not require integral flows for the pairs. This problem is APX-hard even for trees, and a 2-approximation algorithm is known for trees. For general graphs, Chekuri et al. (STOC´04) give a poly-logarithmic factor approximation algorithm and show that a natural LP-relaxation has a poly-logarithmic integrality gap. This result is in contrast with the integrality gap Ω(√n) for the maximum edge-disjoint paths problem. Our main result considerably strengthens this result when an input graph is planar. Namely, for the all-or-nothing multicommodity flow problem in planar graphs, we give an O(1)-approximation algorithm and show that the integrality gap is O(1). In particular, in polynomial time, we can find an index set W with |W| = Ω(OPT) and eight s_i-t_i paths for each i in W such that each edge is used at most eight times in these paths (with multiplicity), where OPT is the optimal value of the LP-relaxation of the all-or-nothing multicommodity flow problem. Our result can be compared to the recent result by S´eguin-Charbonneau and Shepherd (FOCS´11) who give an O(1)-approximation algorithm for the maximum edge-disjoint paths problem in planar graphs with congestion 2 (but not implied by this result).