弦图和近弦图中支配集问题的参数化复杂性与不可近似性
Parameterized Complexity and Inapproximability of Dominating Set Problem in Chordal and Near Chordal Graphs.
作者信息
Liu Chunmei, Song Yinglei
机构信息
Dept. of Systems and Computer Science, Howard University, Washington, DC 20059, USA
出版信息
J Comb Optim. 2010 Apr 15;20(2):1-15. doi: 10.1007/s10878-010-9317-7.
In this paper, we study the parameterized complexity of Dominating Set problem in chordal graphs and near chordal graphs. We show the problem is W[2]-hard and cannot be solved in time in chordal and -chordal ( > 3) graphs unless W[1]=FPT. In addition, we obtain inapproximability results for computing a minimum dominating set in chordal and near chordal graphs. Our results prove that unless NP=P, the minimum dominating set in a chordal or -chordal ( > 3) graph cannot be approximated within a ratio of [Formula: see text] ln in polynomial time, where is the number of vertices in the graph and 0 < c < 1 is the constant from the inapproximability of the minimum dominating set in general graphs. In other words, our results suggest that restricting to chordal or -chordal graphs can improve the approximation ratio by no more than a factor of 3. We then extend our techniques to find similar results for the Independent Dominating Set problem and the Connected Dominating Set problem in chordal or near chordal graphs.
在本文中，我们研究弦图和近似弦图中支配集问题的参数化复杂度。我们证明该问题是W[2] - 难的，并且在弦图和k - 弦图（k > 3）中无法在时间内求解，除非W[1]=FPT。此外，我们得到了关于计算弦图和近似弦图中最小支配集的不可近似性结果。我们的结果证明，除非NP = P，在弦图或k - 弦图（k > 3）中，最小支配集在多项式时间内无法以[公式：见文本]ln 的比率近似，其中n是图中的顶点数，0 < c < 1是一般图中最小支配集不可近似性的常数。换句话说，我们的结果表明，限制在弦图或k - 弦图上，近似比率的提升不超过3倍。然后，我们扩展我们的技术，以在弦图或近似弦图中为独立支配集问题和连通支配集问题找到类似的结果。
Zotero 插件