Weighted Treedepth is NP-complete on Graphs of Bounded Degree
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918322384142336 |
|---|---|
| author | Dirks, Jona Schirrmacher, Nicole Siebertz, Sebastian Vigny, Alexandre |
| author_facet | Dirks, Jona Schirrmacher, Nicole Siebertz, Sebastian Vigny, Alexandre |
| contents | A treedepth decomposition of an undirected graph $G$ is a rooted forest $F$ on the vertex set of $G$ such that every edge $uv\in E(G)$ is in ancestor-descendant relationship in $F$. Given a weight function $w\colon V(G)\rightarrow \mathbb{N}$, the weighted depth of a treedepth decomposition is the maximum weight of any path from the root to a leaf, where the weight of a path is the sum of the weights of its vertices. It is known that deciding weighted treedepth is NP-complete even on trees. We prove that weighted treedepth is also NP-complete on bounded degree graphs. On the positive side, we prove that the problem is efficiently solvable on paths and on 1-subdivided stars. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_18584 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Weighted Treedepth is NP-complete on Graphs of Bounded Degree Dirks, Jona Schirrmacher, Nicole Siebertz, Sebastian Vigny, Alexandre Discrete Mathematics A treedepth decomposition of an undirected graph $G$ is a rooted forest $F$ on the vertex set of $G$ such that every edge $uv\in E(G)$ is in ancestor-descendant relationship in $F$. Given a weight function $w\colon V(G)\rightarrow \mathbb{N}$, the weighted depth of a treedepth decomposition is the maximum weight of any path from the root to a leaf, where the weight of a path is the sum of the weights of its vertices. It is known that deciding weighted treedepth is NP-complete even on trees. We prove that weighted treedepth is also NP-complete on bounded degree graphs. On the positive side, we prove that the problem is efficiently solvable on paths and on 1-subdivided stars. |
| title | Weighted Treedepth is NP-complete on Graphs of Bounded Degree |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2510.18584 |