Polynomial-time conjecture for Hamiltonian cycles after adding fixed vertices

About 6 years old · traced to

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.

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

Never refreshed

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.