Bang-Jensen and Gutin's longest path algorithm conjecture for semicomplete digraphs

From papers

Let DD be a semicomplete digraph, and let x,yx,y be distinct vertices of DD. A longest (x,y)(x,y)-path is an (x,y)(x,y)-path containing the maximum possible number of arcs. Longest path algorithm conjecture. There exists a polynomial algorithm for finding a longest (x,y)(x,y)-path when the input is a semicomplete digraph DD and x,yx,y are distinct vertices of DD. The complexity of finding such a path is stated to be open, even for semicomplete digraphs; the conjecture asks for a polynomial-time algorithm.

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

Jørgen Bang-Jensen, Yun Wang and Anders Yeo, “Generalized paths and cycles in semicomplete multipartite digraphs”, arXiv:2403.07597 (2024).

Solutions 0

No solutions have been posted yet.