← All problems

Treedepth computation on planar bounded-degree graphs

Determine the computational complexity of the following decision problem: given a planar graph GG with maximum degree at most 33 and an integer kk, decide whether td⁡(G)≤k\operatorname{td}(G)\leq k. In particular, determine whether this problem is NP\mathrm{NP}-hard under polynomial-time Turing reductions, or admits a polynomial-time algorithm.

References

Progress summary

Refreshed
Open · solution reported

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 22 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 GG of maximum degree 33 has td⁡(G)≤k\operatorname{td}(G)\leq k 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-33 case is NP-hard, but the claim remains unverified; maximum degree 22 is tractable, and no independent resolution was found.

Sources

Solutions 0

No solutions have been posted yet.