Polynomial algorithm for fixed-k induced detours

Question 1.5 · arXiv:2005.12861

arXiv Question high confidence— first stated 2020-05-26

Authors: Eli Berger, Paul Seymour, Sophie Spirkl

Status open medium confidence

Question 1.5 asks whether, for fixed k>1, there is a polynomial-time algorithm deciding if a graph G contains an induced uv-path of length at least d(u,v)+k. The source paper resolves k=1 (Theorem 1.1, running in O(n^18)) and notes the algorithm can be adjusted for k=2, leaving k≥3 explicitly open. A follow-up by Chiu and Lu (STACS 2022; Information and Computation 2024, arXiv:2109.15268) improves the k=1 algorithm to O(n^4.75) via Boolean matrix multiplication, but does not address the k≥3 case. No resolution of the k≥3 question was found in the indexed literature.

Cited literature (1)

partial Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-shortest Induced Paths (2024)

Yung-Chung Chiu, Hsueh-I Lu · Information and Computation · arXiv:2109.15268

Improves the k=1 algorithm of Berger-Seymour-Spirkl from O(n^18) to O(n^4.75) using a poly-logarithmic number of n²×n² Boolean matrix multiplications; does not address Question 1.5 for k≥3.

Reviewer notes. The k=1 case (any induced non-shortest uv-path) was settled by the source paper itself; k=2 is also handled by a minor adjustment of the same algorithm. The question is open for all k≥3. Chiu-Lu (2022/2024) is the only confirmed follow-up and concerns runtime improvement for k=1 only.

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

Question. For fixed $k > 1$, is there a polynomial-time algorithm that, given a graph $G$ and $u, v \in V(G)$, decides whether there is an induced $uv$-path $P$ in $G$ of length at least $d(u, v) + k$?

Context

The paper's main result (Theorem 1.1) gives a polynomial-time algorithm for the case $k = 1$ (detecting any induced non-shortest path), and the authors note the algorithm can be adjusted for $k = 2$. The question remains open even for $k = 3$. Fixing $k$ is necessary, since Theorem 1.6 shows the problem is NP-hard when $k$ is part of the input (e.g., deciding whether there exists a $uv$-NSP of length at least $2d_G(u,v)$).

Source paper

Finding an induced path that is not a shortest path
Eli Berger, Paul Seymour, Sophie Spirkl · 2020-05-26
https://arxiv.org/abs/2005.12861 PDF source