圓形圖上完全支配問題的近似演算法

Approximation Algorithms for the Total Domination Problem on Circle Graphs

王柏元(Po-Yuan Wang)

指導教授 ： 陳健輝 ； 林清池

國立臺灣大學/電機資訊學院/資訊工程學系/碩士(2022年)

https://doi.org/10.6342/NTU202210104

摘要

支配問題是在給定的圖中尋找該圖點集的一個最小子集，使得圖上所有不屬於該子集的點，皆有至少一鄰居屬於該子集。完全支配問題則是在圖上尋找該圖點集的一個最小子集，使得圖上所有點皆有至少一鄰居屬於該子集。此二問題在圓形圖上皆為 NP-complete。Mirela 和 Sriram 為支配問題提出了一時間複雜度為 O(n^2) 的 8 倍近似演算法和時間複雜度為 O(n^3+(6/ε)n^(⌈1+6/ε⌉)m) 的 (2+ε) 倍近似演算法，亦為完全支配問題提出了時間複雜度為 O(n^4+(6/ε)n^(⌈1+6/ε⌉)m) 的 (3+ε) 倍近似演算法。本篇論文則在此基礎上為完全支配問題提出了時間複雜度為 O(n+m) 的 10 倍近似演算法，並利用 Kratsch 和 Stewart 所提出的轉換方式提出時間複雜度為 O(n^3+(6/ε)n^(⌈1+6/ε⌉)m) 的 (2+ε) 倍近似演算法。

關鍵字

支配問題 ； 完全支配問題 ； 圓形圖 ； 近似演算法

並列摘要

Given a graph, the domination problem is to find a minimum cardinality vertex subset of the graph, such that each vertex not in the subset has at least one neighbor in the subset. Similarly, the total domination problem is to find a minimum cardinality vertex subset of the graph, such that each vertex of the graph have at least one neighbor in the subset. These two problems are both NP-complete on circle graphs. Mirela and Sriram proposed an 8-approximation algorithm with O(n^2) time complexity and a (2+ε)-approximation algorithm with O(n^3+(6/ε)n^(⌈1+6/ε⌉)m) time complexity for the domination problem. They also proposed a (3+ε)-approximation algorithm with O(n^4+(6/ε)n^(⌈1+6/ε⌉)m) time complexity for the total domination problem. Based on their results, we further proposed a 10-approximation algorithm for the total domination problem with O(n+m) time complexity in this thesis. With the transformation proposed by Kratsch and Stewart, we also proposed a (2+ε)-approximation algorithm with O(n^3+(6/ε)n^(⌈1+6/ε⌉)m) time complexity.

並列關鍵字

domination problem ； total domination problem ； circle graph ； approximation algorithms

參考文獻

[1] M. S. Chang, S. Y. Hsieh, and G. H. Chen. Dynamic programming on distancehereditary graphs. In Proceedings of the International Symposium on Algorithms and Computation, pages 344–353. Springer, 1997.

[2] M. S. Chang, S. C. Wu, G. J. Chang, and H. G. Yeh. Domination in distancehereditary graphs. Discrete Applied Mathematics, 116(1-2):103–113, 2002.

[3] L. Chen, C. H. Lu, and Z. B. Zeng. Hardness results and approximation algorithms for (weighted) paired-domination in graphs. Theoretical Computer Science, 410(47-49):5063–5071, 2009.

[4] E. J. Cockayne, R. Dawes, and S. T. Hedetniemi. Total domination in graphs. Networks, 10(3):211–219, 1980.

[5] M. Damian-Iordache and S. V. Pemmaraju. Hardness of approximating independent domination in circle graphs. In Proceedings of the International Symposium on Algorithms and Computation, pages 56–69. Springer, 1999.