Pith. Sign in

REVIEW

Treedepth is NP-Hard on Planar Graphs of Maximum Degree 3

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Kolja Kühn

Discrete Mathematics · Submitted 30 Oct 2026 · 15 references

Pith's verdict: Treedepth's NP-hardness on planar degree-3 graphs is a genuine result; the lower-bound proof is mostly sound, but the wall-minor lemma needs formalization before I'd call it settled.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on November 2, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 3 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv ID2610.42033 (version 1)
Pith IDBLH6B65Z, Pith's permanent record of this paper and its review
CitationKolja K\"uhn. "Treedepth is NP-Hard on Planar Graphs of Maximum Degree 3." arXiv:2610.42033 (2026). https://pith.science/paper/BLH6B65Z
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Computing treedepth is NP-hard even for planar graphs of maximum degree 3, under Turing reductions.

The reading

The paper settles two long-open questions about treedepth — the graph parameter that measures how few rounds of vertex deletion are needed to dismantle a graph — by proving that computing it is NP-hard even when the input is restricted to planar graphs in which every vertex touches at most three edges. Since graphs of maximum degree 2 are disjoint unions of paths and cycles, whose treedepth is easy to decide, the degree bound 3 is the best possible. The proof is a polynomial-time Turing reduction from Weighted Tree Search, a strongly NP-hard problem about locating a hidden vertex in a weighted tree by paying for edge queries. The construction encodes each query cost as a bundle of connecting paths between wall-based vertex gadgets, so that a search strategy of cost at most $K$ becomes a treedepth decomposition of height $2K+1+A$, and any cheaper decomposition would contradict the search-cost lower bound. This matters because algorithms that exploit bounded treedepth typically require a decomposition as input; the paper shows that on planar degree-3 graphs such a decomposition cannot be computed efficiently unless P = NP.

What carries the argument

Four objects carry the argument. The wall $W_k$ — a planar degree-3 grid-like graph with treedepth between $k$ and $4k$ — is the resilient core: Observation 2 states that deleting any single vertex from $W_k$ leaves a minor containing $W_{k-1}$ while preserving a bijection between the terminal vertices, which is exactly what lets the induction survive arbitrary deletions. The double wall $W_k^{(2)}$, two walls joined by a subdivided edge whose subdivision vertex $r$ provably attains the optimal first deletion, is the anchor: it has known treedepth $\mathrm{td}(W_a)+1$, giving the construction its exact counting. The transformation assembles, for each vertex of the source tree, a gadget consisting of a backbone wall carrying $K+1$ anchors, and for each weighted tree edge, that many strand vertices linking the two backbones; a decision tree of cost $K$ is read level-by-level as an elimination tree of height $2K+1+A$. The lower bound is carried by the potential $\Psi(T,c,h) := \min\{f(T,c)+\mu(h), \nu(h)\}$ on generalized $(T,c,h,a)$-graphs, where $h(v)$ counts surviving anchors and $\mu, \nu$ measure the two ways a deletion process can strip anchors; Lemma 13 and Lemma 14 show that deleting any one vertex lowers this potential by at most one, so Theorem 12 forces $\mathrm{td}(H) \ge \Psi + A$.

Extended reading notes

Core claim

The paper's central claim is Theorem 1: under polynomial-time Turing reductions, deciding whether a planar graph of maximum degree 3 has treedepth at most $k$ is NP-hard, so unless P = NP no polynomial-time algorithm for it exists. This answers two previously open questions — whether treedepth remains hard on planar graphs, and whether it remains hard on bounded-degree graphs — in the stronger combined form, and the degree bound is best possible because graphs of maximum degree 2 are disjoint unions of paths and cycles whose treedepth is easily decided. The proof reduces from Weighted Tree Search, a strongly NP-hard problem (quoted from the literature) in which a hidden vertex of a weighted tree must be located by paying for edge queries. Each tree vertex becomes a wall-based gadget with attached anchors, and each weighted edge becomes that many strand vertices between gadgets; a search strategy of cost at most $K$ becomes an elimination tree of height at most $B = 2K+1+A$, and the converse direction is forced by a potential-function induction showing treedepth at least $B+1$ when the search cost exceeds $K$, where $A = \mathrm{td}(W_a)$ is the treedepth of a wall. Because $A$ is not known to be computable, the reduction first recovers it from the oracle by binary search, which the paper identifies as the single obstacle to making the reduction a Karp reduction.

Load-bearing premise

The load-bearing premise is Observation 2, the geometric lemma that deleting any single vertex from a wall $W_k$ still leaves a minor of the smaller wall $W_{k-1}$ with its terminals correctly matched; the lemma is proved by a sketched case analysis with figures, and if any contraction case failed to preserve the $(T,c,h,a)$-graph format, the potential induction behind the lower bound would collapse.

Editorial extensions

If this is right

  • Unless P = NP, computing treedepth — and hence constructing an optimal treedepth decomposition — is impossible in polynomial time on planar graphs of maximum degree 3, resolving both the planar and bounded-degree versions of the open problem at once.
  • The degree bound is best possible: on graphs of maximum degree 2, which are disjoint unions of paths and cycles, treedepth is efficiently decidable, so degree 3 is exactly where hardness begins.
  • Algorithmic metatheorems that run in time $2^{O(d)} n^{O(1)}$ when supplied with a treedepth decomposition of depth $d$ cannot, for this graph class, be made polynomial by first computing the decomposition.
  • The reduction would upgrade from a Turing reduction to a Karp (many-one) reduction as soon as the treedepth of walls $W_k$ is computable in polynomial time — the paper's Question 1 — since $A = \mathrm{td}(W_a)$ is the only quantity the reduction cannot compute on its own.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The two-part potential $\Psi(T,c,h) = \min\{f(T,c)+\mu(h), \nu(h)\}$ encodes a strategy trade-off — isolate all vertices first, or strip anchors while vertices are still connected — that reads like a minimax characterization of weighted tree search; a rigorous game-theoretic reading might extract exact values for search cost on weighted trees, which the paper does not pursue.
  • Observation 2 is a self-contained lemma about walls that may transfer to hardness proofs for other minor-monotone parameters on planar degree-3 graphs; any parameter that is monotone under minors and large on walls could reuse the same deletion-survival argument.
  • The wall's treedepth is only known to lie between $k$ and $4k$, so pinning down an exact formula for $\mathrm{td}(W_k)$ — a concrete finite calculation for each $k$ — is the most direct path to a Karp reduction, and might also identify which wall vertices are optimal roots, which the paper notes are unknown.
  • Whether the anchor role can be played by some other minor-closed family with exactly known treedepth (the paper's Question 2) is a testable design problem: if such a family exists, the Turing-reduction caveat disappears without needing wall treedepth.
Original abstract

Treedepth is an important parameter in algorithmic graph theory. It is known that the problem of computing the treedepth of a graph is NP-hard. It has been an open problem whether treedepth can be computed in polynomial time when the input graph is restricted to be planar, or of bounded degree. Assuming $P \neq NP$, we answer both questions in the negative: Under polynomial-time Turing reductions, it is NP-hard to compute the treedepth of planar graphs with maximum degree 3. This degree bound is best possible, since treedepth can be computed efficiently on graphs of maximum degree 2.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-02: 1 request, 4,216 input tokens.

What the abstract itself states, as probabilities: claims first 0.09 · states limitation 0.48 · human participants 0.01 · controlled comparison 0.03 · randomized assignment 0.01 · states quantitative result 0.85 · compares with prior results 0.78 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

Treedepth is an important parameter in algorithmic graph theory. It is known that the problem of computing the treedepth of a graph is NP-hard. It has been an open problem whether treedepth can be computed in polynomial time when the input graph is restricted to be planar, or of bounded degree. Assuming $P \neq NP$, we answer both questions in the negative: Under polynomial-time Turing reductions, it is NP-hard to compute the treedepth of planar graphs with maximum degree 3. This degree bound is best possible, since treedepth can be computed efficiently on graphs of maximum degree 2.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 Treedepth is an important parameter in algorithmic graph theory. background 1.00 0.04 0.01 asserted 1.00
s1 It is known that the problem of computing the treedepth of a graph is NP-hard. background 1.00 0.04 0.03 asserted 1.00
s2 It has been an open problem whether treedepth can be computed in polynomial time when the input graph is restricted to be planar, or of bounded degree. gap 1.00 0.03 0.03 asserted 0.88
s3 Assuming $P \neq NP$, we answer both questions in the negative: Under polynomial-time Turing reductions, it is NP-hard to compute the treedepth of planar graphs with maximum degree 3. result 0.87 0.91 0.97 asserted 0.99
s4 This degree bound is best possible, since treedepth can be computed efficiently on graphs of maximum degree 2. result 0.56 0.35 0.06 asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 0.98.

What was examined, and what was not

sources read
  • arXiv listing abstract v1
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 1. The 4 × 4 wall W4. We label the paths by letters, so b1 = (2, 1). ▶ Theorem 1. Treedepth on Planar Graphs of Degree at most 3 is NP-hard under polynomial-time Turing reductions. In particular, unless P = NP, there is no polynomial-time algorithm that decides for a given planar graph G with maximum degree 3 and an integer k, whether td(G) ≤ k. This paper is organized as follows. We give some basic definitions and simple observations in Section 2. In Section 3 we describe the polynomial transformation used in the reduction. Section 4 shows the main result: Treedepth on Planar Graphs…
Figure 2. A minor model of W3 in W4 − v for v = b5 = (2, 5), as in Observation 2. Dashed vertices and edges are deleted. Red are branch sets of the first family, blue are branch sets of the second family, remaining vertices are singleton branch sets. Terminals are drawn with thick vertex boundaries. For the second step, we first consider the main case where 1 < i < k and ℓ < k. Then define in H the following three families of branch sets: 1. For each i ′ ̸= i the branch set {(i ′ , 2ℓ − 1),(i ′ , 2ℓ),(i ′ , 2ℓ + 1)}, highlighted in red in
Figure 3. Left: The wall W3. Right: The double wall W (2) 3 with root r. Note that W (2) 3 has maximum degree 3. Weighted Tree Search A weighted tree (T, c) has a weight function c : E(T) → N which assigns to each edge of the tree T a positive integer weight. We further define c(T) := P e∈E(T) c(e). In the Weighted Tree Search problem, we are given a weighted tree (T, c) and a budget K, and the goal is to find a secret vertex v ∈ V (T) using the following operation. We may query any edge e of T at cost c(e), to reveal in which of the two connected components of T − e the secret vertex v li
Figure 4. Transforming an instance of Weighted Tree Search to one of Treedepth on Planar Graphs of Degree at most 3. It remains to connect the vertex gadgets according to the tree T. For each edge uv ∈ E(T) the graph G contains c(uv) connecting strand vertices. Each strand vertex is adjacent to one terminal of Wu and one terminal of Wv. More precisely, the c(uv) strand vertices are connected to a contiguous interval of c(uv) terminals of Wu and Wv, in opposite orders. This allows the nested drawing of strand vertices shown in
Figure 5. The modification of graph H in Lemma 13, when deleting a strand vertex. The terminals x ′ and x ′′ are deleted and the branch sets contracted. The purple branch set is the special case of the two merged branch sets of Observation 2. Consider first the case where x is vertex (i, j) of some vertex backbone Wv, i.e., contained in that wall’s path Pi , and that the terminal of Pi is connected to some anchor for vertex v. In this case, define as H′ the graph obtained from H by deleting the connected anchor and contracting Wv − x according to Observation 2. The resulting graph is of type…

Figures reproduced from arXiv:2610.42033 by the authors.

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.