The maximum-degree conjecture for extreme points of the Held–Karp relaxation

About 16 years old · traced to

Consider extreme points of the Held–Karp relaxation on nn 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 nn vertices is exactly

⌈n2⌉.\left\lceil\frac{n}{2}\right\rceil.

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.