Papers for

software engineers optimizing graph-based data structures

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Graph search tree leaf count optimization remains complex for lexicographic DFS

On Kernels and Leaves: Searching for Bare and Lush Trees

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.

Thu 24 SeptData Structures and AlgorithmsComputational ComplexityDiscrete Mathematics
The gist
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.
Open → 2609.29451v1