Metraipolis › archive › dc_cb1898245cce

On Kernels and Leaves: Searching for Bare and Lush Trees — arXiv:2609.29451

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.29451
License (as archived)
CC0-1.0
Archived
2026-10-08T07:26:41.119Z
SHA-256 of the archived text
1fd7d2446f766efb97c3aca27f2a59bf39d05cfb4067e53c838ec78ff757c223
Stable URL of this page
https://metraipolis.com/documento/dc_cb1898245cce

How to cite

On Kernels and Leaves: Searching for Bare and Lush Trees — arXiv:2609.29451 — arXiv (en), https://arxiv.org/abs/2609.29451 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cb1898245cce (Metraipolis archive dc_cb1898245cce, sha256 1fd7d2446f766efb97c3aca27f2a59bf39d05cfb4067e53c838ec78ff757c223)
BibTeX
@misc{dccb1898245cce,
  title = {On Kernels and Leaves: Searching for Bare and Lush Trees — arXiv:2609.29451},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.29451},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cb1898245cce; sha256 1fd7d2446f766efb97c3aca27f2a59bf39d05cfb4067e53c838ec78ff757c223},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.29451. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-25 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC); Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.29451 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T06:44:29.088Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).