Constant-congestion integrality-gap conjecture for maximum edge-disjoint paths in minor-closed families
Let 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 when congestion 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.