The maximum-degree conjecture for extreme points of the Held–Karp relaxation
The maximum-degree conjecture for extreme points of the Held–Karp relaxation
Consider extreme points of the Held–Karp relaxation on vertices, and let the maximum degree of an extreme point mean the maximum degree of its support graph. The maximum-degree conjecture. The maximum degree of extreme points on vertices is exactly
The paper derives examples with large support degree and presents this claim as a conjecture based on enumeration through 12 vertices; whether the upper bound holds in general remains open.
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
David Pritchard, “k-Edge-Connectivity: Approximation and LP Relaxation”, arXiv:1004.1917 (2010).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.