Edge-Disjoint Paths in Planar Graphs with Constant Congestion

We study the maximum edge disjoint path problem in undirected planar graphs: given a graph G and node pairs s_1t_1,s_2t_2,…,s_kt_k the goal is to maximize the number of pairs that can be connected (routed) by edge-disjoint paths. The natural multicommodity flow relaxation has an Omega(sqrt{n}) integrality gap. Motivated by this, we consider solutions with constant congestion for some small c > 1; that is, solutions in which up to c paths are allowed to use an edge (alternatively, each edge has a capacity of c). In previous work we obtained an log(n) approximation with congestion 2 via the flow relaxation. This was based on a method of decomposing into well-linked subproblems. In this paper we obtain a constant factor approximation with congestion 4.To obtain this improvement we develop an alternative decomposition that is specific to planar graphs. The decomposition produces instances that we call Okamura-Seymour (OS) instances. These have the property that all terminals lie on a single face. Another ingredient we develop is a constant factor approximation for the all-or-nothing flow problem on OS instances via the flow relaxation. We also study limitations on the approximation that can be achieved by a well-linked decomposition. For general graphs we show a lower bound of Omega(log (n)/log log (n)). For planar graphs we describe instances that suggest a super-constant lower bound.