An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs
Ken‐ichi Kawarabayashi, Yusuke Kobayashi · ACM Transactions on Algorithms · 2013
In this article, we study an approximation algorithm for the maximum edge-disjoint paths problem. In this problem, we are given a graph and a collection of pairs of vertices, and the objective is to find the maximum number of pairs that can be connected by edge-disjoint paths. We give an O (log n )-approximation algorithm for the maximum edge-disjoint paths problem when an input graph is either 4-edge-connected planar or Eulerian planar. This improves an O (log 2 n )-approximation algorithm given by Kleinberg [2005] for Eulerian planar graphs. Our result also generalizes the result by Chekuri et al. [2004, 2005] who gave an O (log n )-approximation algorithm for the maximum edge-disjoint paths problem with congestion two when an input graph is planar.