The polynomial-size DFJ relaxation conjecture for cubic graphs

About 7 years old · traced to

Let ammaamma be a cubic graph. Let MathcalPb Mathcal{P}_b be the feasible region defined by constraints

−−--

, and let MathcalPc Mathcal{P}_c be the feasible region defined by the degree, subtour, symmetry, upper-bound, and nonnegativity constraints

−−--

, where SS ranges over proper subsets of the vertices of ammaamma. Polynomial-size DFJ relaxation conjecture. The constraints

−−--

form a polynomial-size set equivalent to the exponential-size set

−−--

; equivalently, Pb=Pc\mathcal{P}_b=\mathcal{P}_c. If true, this would provide a polynomial-size description of the DFJ feasible region for every cubic graph. The claim is motivated only by computational comparisons in the source, which reports that the two formulations identified exactly the same tested non-Hamiltonian graphs; no resolution is given.

References

Primary source

Jerzy A Filar, Michael Haythorpe and Serguei Rossomakhine, “A New Heuristic for Detecting Non-Hamiltonicity in Cubic Graphs”, arXiv:1902.10342 (2019).

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.