Poly-time excess-3 induced st-path detection
Open Problem (induced st-path of excess length three) · arXiv:1904.12273
Status open high confidence
No polynomial-time algorithm and no NP-hardness proof is known for detecting an induced st-path of length at least three more than the shortest st-path. The related and strictly easier problem of excess ≥ 1 was solved in polynomial time by Berger, Spirkl, and Seymour (arXiv:2005.12861, 2020), with the running time subsequently improved from O(n^{18}) to O(n^{4.75}) by Chiu and Lu (arXiv:2109.15268, 2021); neither work addresses excess ≥ 3 or the intermediate case of excess ≥ 2.
Cited literature (1)
-
partial Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-shortest Induced Paths (2021)
Improves the polynomial algorithm for detecting an induced st-path longer than the shortest (excess ≥ 1) from O(n^{18}) to O(n^{4.75}) via Boolean matrix multiplications, but does not address the open problem of excess ≥ 3.
Reviewer notes. No follow-up resolving the excess ≥ 3 case was found. The contemporaneous paper arXiv:2005.12861 (Berger, Spirkl, Seymour; arXiv 2020, journal Discrete Mathematics 2021) solved the easier excess ≥ 1 problem polynomially. The intermediate cases (excess = 2 or excess = 3) remain open with no complexity determination in the indexed literature.
Context
Berger, Spirkl, and Seymour (including a co-author of the present paper) have a poly-time algorithm to detect an induced $st$-path longer than the shortest $st$-path. Whether a poly-time algorithm exists to detect one that is at least three longer remains open, as noted in the introduction.
Notes. Stated in passing as 'It is open whether...' with no formal label. Arises from related work by Berger, Spirkl, and Seymour; one of the present paper's authors (Seymour) is involved in the related work.
Source paper
Detecting a long odd hole
Maria Chudnovsky, Alex Scott, Paul Seymour · 2020-09-06
https://arxiv.org/abs/1904.12273
PDF source