Metraipolis › archive › dc_ecfb019dcf24

Treedepth is NP-Hard on Planar Graphs of Maximum Degree 3 — arXiv:2610.42033

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.42033
License (as archived): CC0-1.0
Archived: 2026-11-03T05:45:21.659Z
SHA-256 of the archived text: fefb48387dbb873901e0dea92036c0c9c3ffbc19d76d8fabc559529a872dcfeb
Stable URL of this page: https://metraipolis.com/documento/dc_ecfb019dcf24

How to cite

Treedepth is NP-Hard on Planar Graphs of Maximum Degree 3 — arXiv:2610.42033 — arXiv (en), https://arxiv.org/abs/2610.42033 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ecfb019dcf24 (Metraipolis archive dc_ecfb019dcf24, sha256 fefb48387dbb873901e0dea92036c0c9c3ffbc19d76d8fabc559529a872dcfeb)

BibTeX

@misc{dcecfb019dcf24,
  title = {Treedepth is NP-Hard on Planar Graphs of Maximum Degree 3 — arXiv:2610.42033},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.42033},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ecfb019dcf24; sha256 fefb48387dbb873901e0dea92036c0c9c3ffbc19d76d8fabc559529a872dcfeb},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.42033. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Computational Complexity (cs.CC); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.42033 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T05:32:17.023Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).