Constant-congestion integrality-gap conjecture for maximum edge-disjoint paths in minor-closed families
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.
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
Sign in to submit a solution.
No solutions have been posted yet.