Polynomial-time conjecture for Hamiltonian cycles after adding fixed vertices

From papers

A semicomplete digraph is a digraph in which every pair of distinct vertices is joined by at least one directed arc. Fix an integer kk. Consider digraphs obtained from a semicomplete digraph by adding kk new vertices and an arbitrary set of arcs involving the new vertices.

Conjecture on fixed-vertex extensions. For every fixed integer kk, 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 k=2k=2. 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

No solutions have been posted yet.