2025/10/21 by Jona Dirks, Nicole Schirrmacher, Dirks, Jona +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2510.18584
openalex publication_date 2025/10/21 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
A treedepth decomposition of an undirected graph G is a rooted forest F on the vertex set of G such that every edge uv∈ E(G) is in ancestor-descendant relationship in F. Given a weight function w\colon V(G)→ ℕ, 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.