Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2301.12783 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915920723574784 |
|---|---|
| author | Baste, Julien |
| author_facet | Baste, Julien |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_12783 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Leafed Induced Subtree in chordal and bounded treewidth graphs Baste, Julien Data Structures and Algorithms 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. |
| title | The Leafed Induced Subtree in chordal and bounded treewidth graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2301.12783 |