The polynomial-size DFJ relaxation conjecture for cubic graphs
The polynomial-size DFJ relaxation conjecture for cubic graphs
Let be a cubic graph. Let be the feasible region defined by constraints
, and let be the feasible region defined by the degree, subtour, symmetry, upper-bound, and nonnegativity constraints
, where ranges over proper subsets of the vertices of . Polynomial-size DFJ relaxation conjecture. The constraints
form a polynomial-size set equivalent to the exponential-size set
; equivalently, . 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
Sign in to submit a solution.
No solutions have been posted yet.