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.
References
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.
Progress summary
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.