Spanheight, A Natural Extension of Bandwidth and Treedepth
N. van Roden · 2015
In graph theory, the bandwidth problem has a long history, and a number of practical applications. Fomin, Heggernes, and Telle [20] introduced treespan, an extension from bandwidth to depth first search spanning trees in the context of the occupancy measure in search games. It is the equivalent of a tree-decomposition, where adjacent bags differentiate with at most 1 vertex, and each vertex is only allowed to appear in at most k bags. Dregi [16] explored parameterized algorithms for treespan under the name adjacencyspan. In this thesis, we define spanheight as a different extension from bandwidth to depth first search spanning trees. A spanheight-decomposition is a DFS spanning tree, in which every pair of adjacent vertices are connected with a path of length at most k + 2. It is the equivalent of a tree-decomposition, where adjacent bags differentiate with at most 1 vertex, and the sub-tree induced by bags containing a vertex v has height at most k + 2. We proof spanheight to be NP-Complete. We introduce a single exponential algorithm for k-spanheight using O(n29n) time and O(n22n) space. This algorithm is based on the bucketassignment technique from Feige [17]. Attempting to find an FPT algorithm, we argue that the graph minor theorem and Courcelle’s theorem cannot be used to proof the FPT membership of spanheight. Instead we proof it to be FPT when restricted to graphs of bounded treedepth. Finally we present an O(nt4 · 27t·2·log ) time and O(n · 23t·2·log ) space FPT algorithm by parameterizing on the treedepth t of a graph. A second problem we study is restricted-spanheight, which is a special case of spanheight where the DFS spanning tree is restricted to edges from the input graph. For restrictedspanheight we provide similar results to spanheight. As a side result we look at reconfiguration of DFS spanning trees. The results in this thesis are mainly of theoretical significance, because the presented algorithms are very slow.