Hardness of r-dominating set on Graphs of Diameter (r + 1)
Hardness of r-dominating set on Graphs of Diameter (r + 1)
复制标题
直径图上 r 支配集的硬度 (r 1)
DOI：
10.1007/978-3-319-03898-8_22
复制
发表时间：
2013
期刊：
影响因子：
1.1
通讯作者：
Saket Saurabh
中科院分区：
文献类型：
--
作者：
D. Lokshtanov;Neeldhara Misra;Geevarghese Philip;M. Ramanujan;Saket Saurabh
在参数化的复杂性领域中，主要研究了主导集问题。它是减少的最常见来源之一，同时证明了问题的参数性棘手性。在本文中，我们在参数化复杂性领域中查看在有界直径图上的主导集及其概括的R-domimination集合。我们表明，统治集合在直径2的图上保持w [2] - hard hard hard hard of r + 1的r为w [2] - hard hard r + 1。最好的可能，因为R为R的集合显然是可以在直径图上溶解的多项式时间。
The dominating set problem has been extensively studied in the realm of parameterized complexity. It is one of the most common sources of reductions while proving the parameterized intractability of problems. In this paper, we look at dominating set and its generalization r-dominating set on graphs of bounded diameter in the realm of parameterized complexity. We show that dominating set remains W[2]-hard on graphs of diameter 2, while r-dominating set remains W[2]-hard on graphs of diameter r + 1. The lower bound on the diameter in our intractability results is the best possible, as r-dominating set is clearly polynomial time solvable on graphs of diameter at most r.