Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves

For a given graph G, a depth-first search (DFS) tree T of G is an r-rooted spanning tree such that every edge of G is either an edge of T or is between a descendant and an ancestor in T. A graph G together with a DFS tree is called a lineal topology T = (G, r, T). Sam et al. (2023) initiated study of the parameterized complexity of the MIN-LLT and MAX-LLT problems which ask, given a graph G and an integer k >= 0, whether G has a DFS tree with at most k and at least k leaves, respectively. Particularly, they showed that for the dual parameterization, where the tasks are to find DFS trees with at least n- k and at most n - k leaves, respectively, these problems are fixed-parameter tractable when parameterized by k. However, the proofs were based on Courcelle's theorem, thereby making the running times a tower of exponentials. We prove that both problems admit polynomial kernels with O(k(3)) vertices. In particular, this implies FPT algorithms running in k(O(k))center dot n(O(1)) time. We achieve these results by making use of a O(k)-sized vertex cover structure associated with each problem. This also allows us to demonstrate polynomial kernels for MIN-LLT and MAX-LLT for the structural parameterization by the vertex cover number.