@InProceedings{10.1007/978-3-031-43587-4_28,
author="Sam, Emmanuel
and Bergougnoux, Benjamin
and Golovach, Petr A.
and Blaser, Nello",
editor="Fernau, Henning
and Jansen, Klaus",
title="Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves",
booktitle="Fundamentals of Computation Theory",
year="2023",
publisher="Springer Nature Switzerland",
address="Cham",
pages="392--405",
abstract="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 {\$}{\$}{\backslash}mathcal {\{}T{\}} = (G, r, T){\$}{\$}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{\backslash}ge 0{\$}{\$}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{\$}{\$}n-kand at most {\$}{\$}n-k{\$}{\$}n-kleaves, 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 {\$}{\$}{\backslash}mathcal {\{}O{\}}(k^3){\$}{\$}O(k3)vertices. In particular, this implies FPT algorithms running in {\$}{\$}k^{\{}{\backslash}mathcal {\{}O{\}}(k){\}}{\backslash}cdot n^{\{}O(1){\}}{\$}{\$}kO(k){\textperiodcentered}nO(1)time. We achieve these results by making use of a {\$}{\$}{\backslash}mathcal {\{}O{\}}(k){\$}{\$}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.",
isbn="978-3-031-43587-4"
}