The Leafed Induced Subtree in chordal and bounded treewidth graphs

01/30/2023

∙

by   Julien Baste, et al.

∙

1

∙

share

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.