The polynomial-size DFJ relaxation conjecture for cubic graphs

From papers

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.

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

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

Solutions 0

No solutions have been posted yet.