Back to Search
Start Over
The Leafed Induced Subtree in chordal and bounded treewidth graphs
- Publication Year :
- 2023
-
Abstract
- 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.<br />Comment: arXiv admin note: substantial text overlap with arXiv:1704.07284, arXiv:2103.06536
- Subjects :
- Computer Science - Data Structures and Algorithms
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2301.12783
- Document Type :
- Working Paper