The Leafed Induced Subtree in chordal and bounded treewidth graphs
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |