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.
References
Primary source
David Pritchard, “k-Edge-Connectivity: Approximation and LP Relaxation”, arXiv:1004.1917 (2010).
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.