Theory Seminar

  • Gates&Hillman Centers
  • Luis von Ahn Awesome Classroom 4101
  • Professor
  • The Department of Mathematics and Statistics
  • McGill University

Edge Disjoint Paths in k-Sums of Graphs

We discuss the approximability of the maximum edge-disjoint paths  problem in undirected graphs, which is closely linked to the integrality  gap for its natural multi-commodity flow based relaxation. This gap is  known to be $\Omega(\sqrt{n})$ even for planar graphs due to a  well-known grid example of Garg-Vazirani-Yannakakis.

Kleinberg and Tardos asked: Is a small gap possible if one allows  constant edge congestion? This is indeed possible in two settings (with  constant congestion): a polylog approximation was shown for general  graphs by Chuzhoy, and a constant approximation was shown for planar  graphs.

Two interesting directions remain open. (A) Can edge congestion can be  avoided with a stronger LP formulation? And (B) For which graph families  is there an O(1)-integrality gap with constant edge-congestion (called  the CFCC property)? The most natural conjecture is that any minor-closed  family has the CCFC property.

Given that Robertson and Seymour's characterization for minor-closed families involves k-sums of bounded genus graphs, two building blocks  must be the families of bounded genus graphs and bounded treewidth  graphs. We show that both classes have the CFCC property. In fact for bounded treewidth graphs we show an O(1)-approximation without edge congestion.

For More Information, Please Contact: