Parameterized Algorithms for Steiner Tree and Dominating Set: Bounding the Leafage by the Vertex Leafage
Parameterized Algorithms for Steiner Tree and Dominating Set: Bounding the Leafage by the Vertex Leafage
复制标题
Steiner 树和支配集的参数化算法：通过顶点叶子来限制叶子
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ana Paula Couto da Silva
中科院分区：
文献类型：
--
作者：
C. M. Figueiredo;Raul Lopes;A. Melo;Ana Paula Couto da Silva
.弦图是树的子树的交图，区间图是路的子路的交图，无向路图是树的路的交图的中间类。已知支配集、连通支配集和Steiner树在弦图上是W [2]-硬的，当用解的大小参数化时，并且在区间图上是多项式时间可解的。至于无向路图，所有这些问题都是NP -完全的，当通过解的大小参数化时，除了平凡的XP分类外，参数化复杂性理论中没有任何分类。证明了无向路图的支配集、连通支配集和Steiner树在解的大小为参数时是FPT，而一般弦图的支配集、连通支配集和Steiner树在解的大小加上图的顶点叶数为参数时仍然是FPT，只要给出一个具有最优顶点叶数的树模型.我们示出了Min-LC-VSP问题的参数化的图的叶面积与顶点叶面积加上解决方案的大小之间的关系。
. Chordal graphs are intersection graphs of subtrees of a tree, while interval graphs are intersection graphs of subpaths of a path. Undi-rected path graphs are an intermediate class of graphs, defined as the intersection graphs of paths of a tree. It is known that Dominating Set , Connected Dominating Set , and Steiner Tree are W [2]-hard on chordal graphs, when parameterized by the size of the solution, and are polynomial-time solvable on interval graphs. As for the undirected path graphs, all these problems are known to be NP -complete, and when parameterized by the size of the solution, no classification in the parameterized complexity theory is known apart from the trivial XP classification. We prove that Dominating Set , Connected Dominating Set , and Steiner Tree are FPT for undirected path graphs when parameterized by the size of the solution, and that they continue to be FPT for general chordal graphs when parameterized by the size of the solution plus the vertex leafage of the graph, provided a tree model with optimal vertex leafage is given. We show a relation between the parameterization of Min-LC-VSP problems by the leafage of the graph versus the vertex leafage plus the size of a solution.