Graph search tree leaf count optimization remains complex for lexicographic DFS
On Kernels and Leaves: Searching for Bare and Lush Trees
Data Structures and AlgorithmsComputational ComplexityDiscrete Mathematics
Summary
The paper looks at how to find a path through a network (a graph) that makes the resulting search tree have the most or fewest endpoints (leaves). Normally, a Depth-First Search (DFS) method builds this tree in a specific way, but the authors study a variant called Lexicographic DFS (LDFS). They find that the hard problems for DFS—deciding if you can get many or few leaves—remain just as hard in LDFS. They also show some limits on how much these problems can be simplified (kernelization). Finally, they consider other search methods and find that minimizing certain tree properties can be very hard for those too.
What this means in practice
- •For network algorithm designers: Understand theoretical limits and complexity when designing graph traversal algorithms with controlled leaf counts in search trees.
- •For software engineers optimizing graph-based data structures: Avoid expecting efficient simplifications when tuning search orderings for tree leaf properties in algorithms based on DFS or LDFS.
A theory result. No direct application yet.
Authors
Jesse Beisegel, Ekkehard Köhler, Robert Scheffler, Martin Strehler
Abstract
We study a variation of the classical Maximum (Minimum) Leaf Spanning Tree problem. In many applications, Depth-First Search (DFS) is used to compute a spanning tree of a graph. Such a search tree is constructed by connecting each vertex $v$ with the last vertex the search has visited before $v$ and we call this a last-in tree. By restricting the Maximum (Minimum) Leaf Spanning Tree problem to last-in trees of a graph search, we ask for a search ordering that leads to the largest (smallest) number of leaves in its search tree. Recently, Bergougnoux et al. [Journal of Computer and System Sciences 154 (2025)] have studied the parameterized complexity of these problems for DFS. They showed that the minimization problem is para-$\mathsf{NP}$-hard and the maximization problem is $\mathsf{W}[1]$-hard when parameterized by the number of leaves. When parameterized by the number of internal vertices, both problems have polynomial kernels. Here, we examine whether these results also hold for the variant Lexicographic DFS (LDFS). We show that the hardness results of DFS can be transferred to LDFS. We also present exponential kernels for the number of internal vertices as the parameter. We complement this by showing that polynomial kernels do not exist, unless $\mathsf{NP} \subseteq \mathsf{coNP} / \mathsf{poly}$. We also consider last-in trees of searches that do not follow the DFS scheme. In contrast to (L)DFS, minimizing the number of internal vertices is para-$\mathsf{NP}$-hard for several searches including Breadth-First Search.