A Faster Parameterized Algorithm for Treedepth

摘要

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 width w, and an integer t-decides whether the input graph has treedepth at most t in time 2~(O(wt)•n. We use this to construct further algorithms which do not require a tree decomposition as part of their input: A simple algorithm which decides treedepth in linear time for a fixed t, thus answering an open question posed by Ossona de Mendez and Nesetril as to whether such an algorithm exists, a fast algorithm with running time 2~(O(t~2)• n and an algorithm for chordal graphs with running time 2~(O(t log t) • n.