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

Abstract

支配問題是在給定的圖中尋找該圖點集的一個最小子集，使得圖上所有不屬於該子集的點，皆有至少一鄰居屬於該子集。完全支配問題則是在圖上尋找該圖點集的一個最小子集，使得圖上所有點皆有至少一鄰居屬於該子集。此二問題在圓形圖上皆為 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.