Subcubic H-ISC planarity dichotomy

Conjecture 1.5 · arXiv:2502.05289

arXiv Conjecture high confidence— first stated 2025-02-07

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

Status open high confidence

Conjecture 1.5 from arXiv:2502.05289 proposes that for any subcubic graph $H$, the $H$-ISC problem (detecting $H$ as an induced subdivision) is in $\mathsf{P}$ if and only if $H$ is planar. The source paper provides the key hardness evidence: it exhibits a specific non-planar subcubic graph $H$ for which $H$-ISC is NP-complete (Theorem 3, also appearing as LIPIcs.ICALP.2025.4). No follow-up paper resolving or substantially advancing the full conjecture was found in the literature indexed as of May 2026.

Reviewer notes. The conjecture is supported by the paper's own main result (NP-completeness for a specific non-planar subcubic H) and known polynomial algorithms for planar cases (net, K_4). The ICALP 2025 published version (LIPIcs vol. 334) numbers this as Conjecture 5.1 rather than 1.5. No follow-up resolving the full if-and-only-if characterization was found across three targeted searches.

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

Conjecture. For any subcubic graph $H$, $H$-\textsc{ISC} is in $\mathsf{P}$ if and only if $H$ is planar.

Context

The conjecture is proposed by the paper's authors as a natural open question following their proof that a specific non-planar subcubic graph yields NP-complete induced subdivision containment. It complements known polynomial-time algorithms for planar induced subdivision detection (e.g., for the net and $K_{4}$) and the new hardness results of the paper.

Notes. The 'only if' direction (NP-hardness for non-planar subcubic $H$) implicitly assumes $\mathsf{P}\neq\mathsf{NP}$.

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