Bang-Jensen and Gutin's longest path algorithm conjecture for semicomplete digraphs
Bang-Jensen and Gutin's longest path algorithm conjecture for semicomplete digraphs
Let be a semicomplete digraph, and let be distinct vertices of . A longest -path is an -path containing the maximum possible number of arcs. Longest path algorithm conjecture. There exists a polynomial algorithm for finding a longest -path when the input is a semicomplete digraph and are distinct vertices of . 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
Sign in to submit a solution.
No solutions have been posted yet.