On the parameterized complexity of lineal topologies (depth-first spanning trees) with many or few leaves
Benjamin Bergougnoux, Nello Blaser, Michael R. Fellows, Petr A. Golovach, Frances Rosamond, Emmanuel Sam · Journal of Computer and System Sciences · 2025
This paper considers four problems with possible applications in network design: Given a graph G with | G | = n and an integer k ≥ 0 , does G have a DFS tree with (i) ≤ k leaves, (ii) ≥ k leaves, (iii) ≤ n − k leaves, and (iv) ≥ n − k leaves? We show that all four problems are NP-hard. When parameterized by k , we prove that while (i) is para-NP-hard and (ii) is W[1]-hard, both (iii) and (iv) admit polynomial kernels with O ( k 3 ) vertices, implying FPT algorithms running in k O ( k ) ⋅ n O ( 1 ) time. Our polynomial kernels are based on a O ( k ) -sized vertex cover structure associated with the solution of these problems. As a byproduct, we obtain polynomial kernels for these problems parameterized by the vertex cover number of the input graph.