Complexity gap between induced disjoint paths variants

Informal Question on Complexity Gap Between Induced Disjoint Paths Variants · arXiv:2502.05289

arXiv Informal medium confidence— first stated 2025-02-07

Authors: Pierre Aboulker, Édouard Bonnet, Timothé Picavet, Nicolas Trotignon

Status open high confidence

The informal question asks whether there is a hereditary graph class separating the complexity of Induced k-Disjoint Paths (NP-complete) from Induced Disjoint S–T Paths with |S|=|T|=k (polynomial), with k=2 being the focal case. The source paper (ICALP 2025) motivates this by observing that known polynomial algorithms tend to cover the linkage variant broadly while hardness reductions tend to cover the flow variant; no follow-up resolving or making progress on this separation question was found in the literature as of May 2026.

Reviewer notes. No follow-up found. The conjecture is recent (February 2025, ICALP 2025, DOI 10.4230/LIPIcs.ICALP.2025.4); absence of evidence for resolution is credible at this stage. The DROPS page lists no citing papers that address this open question.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Informal. Is there a hereditary graph class in which Induced $k$-Disjoint Paths is NP-complete but Induced Disjoint $S$–$T$ Paths with $|S|=|T|=k$ is polynomial-time solvable? The case $k=2$ is of particular interest.

Context

The authors observe a structural asymmetry: polynomial-time algorithms in the literature tend to apply more broadly to Induced $k$-Disjoint Paths (the linkage variant), while hardness proofs tend to apply more broadly to Induced Disjoint $S$–$T$ Paths (the flow variant with $|S|=|T|=k$). This raises the question of whether the two problems can be separated in complexity on some hereditary class.

Notes. Appears in running prose with 'we wonder if' in the preamble to the open questions section (context before Conjecture 1.5); no labelled theorem environment.

Source paper

Induced Disjoint Paths Without an Induced Minor
Pierre Aboulker, Édouard Bonnet, Timothé Picavet, Nicolas Trotignon · 2025-02-07
https://arxiv.org/abs/2502.05289