Bruce Shepherd, Professor
Department of Mathematics and Statistics
McGill University

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.