Julien Baste - The Leafed Induced Subtree in chordal and bounded treewidth graphs

dmtcs:11023 - Discrete Mathematics & Theoretical Computer Science, April 7, 2026, vol. 28:2 - https://doi.org/10.46298/dmtcs.11023
The Leafed Induced Subtree in chordal and bounded treewidth graphsArticle

Authors: Julien Baste ORCID

In the Fully Leafed Induced Subtrees, one is given a graph $G$ and two integers $a$ and $b$ and the question is to find an induced subtree of $G$ with $a$ vertices and at least $b$ leaves. This problem is known to be NP-complete even when the input graph is $4$-regular. Polynomial algorithms are known when the input graph is restricted to be a tree or series-parallel. In this paper we generalize these results by providing an FPT algorithm parameterized by treewidth. We also provide a polynomial algorithm when the input graph is restricted to be a chordal graph.

arXiv admin note: substantial text overlap with arXiv:1704.07284, arXiv:2103.06536

https://doi.org/10.46298/dmtcs.11023
Source: arXiv.org:2301.12783
Volume: vol. 28:2
Section: Discrete Algorithms
Published on: April 7, 2026
Accepted on: January 11, 2026
Submitted on: March 3, 2023
Keywords: Data Structures and Algorithms
Licence: arXiv.org - Non-exclusive license to distribute

Share and export

Consultation statistics

This page has been seen 56 times.
This article's PDF has been downloaded 37 times.