@InProceedings{10.1007/978-3-031-30448-4_25,
author="Sam, Emmanuel
and Fellows, Michael
and Rosamond, Frances
and Golovach, Petr A.",
editor="Mavronicolas, Marios",
title="On the Parameterized Complexity of the Structure of Lineal Topologies (Depth-First Spanning Trees) of Finite Graphs: The Number of Leaves",
booktitle="Algorithms and Complexity",
year="2023",
publisher="Springer International Publishing",
address="Cham",
pages="353--367",
abstract="A lineal topology {\$}{\$}{\backslash}mathcal {\{}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) {\$}{\$}{\backslash}le k{\$}{\$}leaves, (ii) {\$}{\$}{\backslash}ge k{\$}{\$}leaves, (iii) {\$}{\$}{\backslash}le n-k{\$}{\$}leaves, and (iv) {\$}{\$}{\backslash}ge 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.",
isbn="978-3-031-30448-4"
}