Treedepth computation on planar bounded-degree graphs
Determine the computational complexity of the following decision problem: given a planar graph with maximum degree at most and an integer , decide whether . In particular, determine whether this problem is -hard under polynomial-time Turing reductions, or admits a polynomial-time algorithm.
References
- Treedepth is NP-Hard on Planar Graphs of Maximum Degree 3 — arXiv — Kolja Kühn
Source: arXiv
Progress summary
A new paper claims to settle the problem by proving hardness for planar graphs with maximum degree three, while degree two remains tractable.
The problem asks for the complexity of computing treedepth on planar graphs with bounded maximum degree. Kolja Kühn claims NP-hardness already at maximum degree three, which would close the sharp degree gap.
Known results
- Graphs of maximum degree are tractable because they are disjoint unions of paths and cycles.
- A related weighted variant is NP-complete on bounded-degree graphs, but does not establish the unweighted planar result.
October 2026 degree-three hardness claim
Kühn's paper claims that deciding whether a planar graph of maximum degree has is NP-hard under polynomial-time Turing reductions. The reduction uses Weighted Tree Search and leaves polynomial-time computation of the wall values open, so a Karp reduction is not obtained. The paper says the reduction idea was suggested by Claude Opus 5.5; this is assistance, not an independently produced proof.
Current status (as of November 2026): A paper claims the planar maximum-degree- case is NP-hard, but the claim remains unverified; maximum degree is tractable, and no independent resolution was found.
Sources
Solutions 0
No solutions have been posted yet.