Constant-congestion integrality-gap conjecture for maximum edge-disjoint paths in minor-closed families

From papers

Let G{\cal G} be any proper minor-closed family of graphs. The constant-congestion integrality-gap conjecture. The integrality gap of the flow LP for maximum edge-disjoint paths is at most a constant cGc_{\cal G} when congestion 22 is allowed. This strengthens the question of whether all minor-closed graph families have a constant-factor constant-congestion integrality gap for maximum edge-disjoint paths; its status is not resolved in the supplied text.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Chandra Chekuri, Guyslain Naves and F. Bruce Shepherd, “Maximum Edge-Disjoint Paths in k-sums of Graphs”, arXiv:1303.4897 (2013).

Solutions 0

No solutions have been posted yet.