On the Parameterized Complexity of the Structure of Lineal Topologies (Depth-First Spanning Trees) of Finite Graphs: The Number of Leaves

Abstract

A lineal topology T = (G, r, T ) of a graph G is an r-rooted depth-first spanning (DFS) tree T of G. Equivalently, this is a spanning tree of G such that every edge uv of G is either an edge of T or is between a vertex u and an ancestor v on the unique path in T from u to r. We consider the parameterized complexity of finding a lineal topology that satisfies upper or lower bounds on the number of leaves of T , parameterized by the bound. This immediately yields four natural parameterized problems: (i) ≤ k leaves, (ii) ≥ k leaves, (iii) ≤ n − k leaves, and (iv) ≥ n − k leaves, where n = |G|. We show that all four problems are NP-hard, considered classically. We show that (i) is para- NP-hard, (ii) is hard for W[1], (iii) is FPT, and (iv) is FPT. Our work is motivated by possible applications in graph drawing and visualization.