NP-completeness of vertex-disjoint paths, stability two
Informal Conjecture (vertex-disjoint paths, stability number two) · arXiv:1604.02317
Status open high confidence
No paper resolving the conjecture has been found in five web searches. The source paper proves a polynomial-time algorithm for fixed k in semicomplete digraphs (stability number 1) and for digraphs partitioned into a bounded number of semicomplete parts, but leaves the fixed-k, stability-number-two case open with a suspicion of NP-completeness. A 2025 ICALP paper (Gomes, Lopes, Sau) revisits directed disjoint paths on tournaments and corrects a historical NP-completeness proof for unbounded k, but does not address the fixed-k question at stability number two.
Reviewer notes. The conjecture is stated informally in arXiv:1604.02317 (published 2018-12-23). The ICALP 2025 paper 'Revisiting Directed Disjoint Paths on Tournaments (And Relatives)' by Gomes, Lopes, and Sau (https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.90) corrects a 1992 NP-completeness proof for the unbounded-k case on tournaments and provides new FPT algorithms with vertex congestion, but does not resolve the fixed-k stability-number-two conjecture. No follow-up settling the conjecture was found after 5 web calls.
Context
The authors discuss whether their polynomial-time result for semicomplete digraphs (Theorem 1.2) can be extended to digraphs with bounded stability number. The edge-disjoint version is known to be polynomial-time solvable in this setting, but the vertex-disjoint version remains out of reach. The authors remark that they suspect NP-completeness already at stability number two.
Notes. Stated as 'we suspect' in running prose with no labelled theorem environment. The full paper text appears truncated after Section 3; additional conjectures or open problems in later sections may have been missed.
Source paper
Disjoint paths in unions of tournaments
Maria Chudnovsky, Alex Scott, Paul Seymour · 2018-12-23
https://arxiv.org/abs/1604.02317
PDF source