Polynomial-time conjecture for Hamiltonian cycles after adding fixed vertices
Polynomial-time conjecture for Hamiltonian cycles after adding fixed vertices
A semicomplete digraph is a digraph in which every pair of distinct vertices is joined by at least one directed arc. Fix an integer . Consider digraphs obtained from a semicomplete digraph by adding new vertices and an arbitrary set of arcs involving the new vertices.
Conjecture on fixed-vertex extensions. For every fixed integer , there exists a polynomial-time algorithm for deciding whether such a digraph has a Hamiltonian cycle.
The source states that this conjecture is open already for . The resulting digraph need not be a split digraph because arcs may be added between the new vertices.
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
Joergen Bang-Jensen and Yun Wang, “Strong arc decompositions of split digraphs”, arXiv:2309.06904 (2023).
Additional references
2 papers in this index state this conjecture (2020–2023). The statement above is taken from the most recent of them; the others are arXiv:2009.13184.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.