加载中…
In the Fully Leafed Induced Subtrees, one is given a graph and two integers and and the question is to find an induced subtree of with vertices and at least leaves. This problem is known to be NP-complete even when the input graph is -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.

生成讲解博客的中文版本

生成AI智能校验的中文版本