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

At least 12 years old · documented by

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.