2014/01/29 by Felix Reidl, Peter Rossmanith, Reidl, Felix +5 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1401.7540
openalex publication_date 2014/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The width measure treedepth, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence of interest. We present an algorithm which---given as input an n-vertex graph, a tree decomposition of the graph of width w, and an integer t---decides Treedepth, i.e. whether the treedepth of the graph is at most t, in time 2O(wt) ⋅ n. If necessary, a witness structure for the treedepth can be constructed in the same running time. In conjunction with previous results we provide a simple algorithm and a fast algorithm which decide treedepth in time 2^2O(t) ⋅ n and 2O(t2) ⋅ n, respectively, which do not require a tree decomposition as part of their input. The former answers an open question posed by Ossona de Mendez and Nesetril as to whether deciding Treedepth admits an algorithm with a linear running time (for every fixed t) that does not rely on Courcelle's Theorem or other heavy machinery. For chordal graphs we can prove a running time of 2O(t log t)⋅ n for the same algorithm.