圖形最佳化與幾何展開問題之計算方法研究

Algorithms on Graph Optimization and Unfolding Problems

柳青浩(Ching-Hao Liu)

指導教授 ： 潘雙洪

國立清華大學/電機資訊學院/資訊工程學系/博士(2015年)

https://doi.org/10.6843/NTHU.2015.00379

摘要

在數位時代，圖形理論(專門研究圖形的學門)的研究結果已被廣泛運用在資訊科學領域，尤其是網路計算上。隨著社群媒體如Facebook或Twitter等的使用普及和持續成長，社群運算已經變成近年來一個關鍵的研究領域。因此，圖形理論在實務上的重要性也隨之更加提昇。在這本論文中，我們探討兩個與圖形理論相關的研究領域。其一是「圖形最佳化問題」的研究，這是圖形理論中的一個主要研究領域。其二是「幾何展開問題」的研究，這是圖形理論的一個延伸研究領域，其研究結果可被應用到機器人手臂的動作規劃和蛋白質展開的研究上。透過對這兩類問題的一併探索，我們期望建立兩方研究之間的橋梁。

一開始，先介紹我們對「圖形最佳化問題」的研究。我們針對兩個重要問題 (a) 「最小支配集問題」和 (b) 「最大獨立集問題」以及其相關變化形進行討論。對前者，我們探討「最小支配集問題」、「最小獨立支配集問題」、「最小加權獨立支配集問題」。對此，我們最重要的兩個研究成果是：
(i) 對「最小支配集問題」和「最小獨立支配集問題」在 subcubic graphs 上分別設計出有效率的FPT-演算法。

(ii) 證明了「最小支配集問題」和「最小獨立支配集問題」在 cubic bipartite graphs 上都是NP-完全的。

對後者，我們探討「最大獨立集問題」的變化形---「最大邊獨立集問題」。對此，我們最重要的研究成果是對「最大邊獨立集問題」在 cographs 和 distance-hereditary graphs 上分別設計出$O(n^2)$-時間的最佳解演算法($n$是目標圖形的總點數)。

接下來，我們介紹對「幾何展開問題」的研究。我們研究的重心是在「二維平面上的樹鏈結的展開」，主要研究目標有二。首先，我們希望找出樹鏈結之所以會被鎖住的根本性質。因此我們尋找「最小邊數、最小半徑、最小點度數、或是前面這些條件混合下會被鎖住的樹鏈結」的個例。
對此，我們最重要的成果是證明了「被鎖住的線性樹鏈結」的最小邊數就是$8$。

再者，我們討論「$k$-單調線性樹鏈結的展開」。我們的目標是找出「在固定$k$值下，所有的$k$-單調線性樹鏈結皆可被展開」的最大$k$值。為了這個目標，我們一方面設計有效率的展開演算法，另一方面，我們也尋找被鎖住的個例。最後，我們對此最重要的成果是證明了前面提到的最大$k$值就是$4$。

關鍵字

圖形最佳化演算法 ； 支配集 ； 獨立支配集 ； 邊獨立集 ； 幾何展開演算法 ； 最小被鎖住的樹鏈結 ； $k$單調線性樹鏈結

並列摘要

In the digital age, the research results of graph theory (the study of graphs) has been widely used in domains of computer science, especially in network computing. With the widespread and glowing use of social media, such as Facebook and Twitter, social computing has become a key research area in the recent years, and the importance of graph theory in practical aspects is thus further increasing. In this thesis, we study two areas relating to graph theory. One is the study of ``graph optimization problems'', which is a primary research area in graph theory, and the other is the study of ``geometric unfolding problems'', which is an extended research area of graph theory. The results for the latter can be applied to areas such as robot arm motion planning and protein unfolding. Through studying the two areas together, we hope for closing the gap between them.

We here begin with introducing our study on ``graph optimization problems''. We focus on two important problems, that is, (a) the (minimum) dominating set problem and (b) the (maximum) independent set problem, and their variants. For the former, we investigate ``the (minimum) dominating set problem'', ``the (minimum) independent dominating set problem'', and
``the (minimum) weighted independent dominating set problem''. The two most important results for this part are as follows:
(i) We present efficient FPT-algorithms for solving both the dominating set problem and the independent dominating set problem on subcubic graphs, respectively.

(ii) We show that both the dominating set problem and the independent dominating set problem are both NP-complete for cubic bipartite graphs.

For the latter, we consider a variant of ``the (maximum) independent set problem''---the (maximum) edge-independent set problem. The most important result for the part is that we present $O(n^2)$-time algorithms for solving the edge-independent set problem on cographs and distance-hereditary graphs, respectively, where $n$ is the number of vertices of the given graph.

Next, we introduce our study on ``geometric unfolding problems'' in the following. We focus on ``the unfolding of tree linkages in two dimensions'' and there are two main goals. First, we aim to uncover the fundamentals of the lockedness of tree linkages. For this goal, we search for locked instances of ``tree linkages with the smallest size, diameter, degree, or combination of the aforementioned''. The most important result for this part is that we determine that the minimum number of edges for locked linear tree linkages is exactly $8$.

Second, we consider ``the unfolding of $k$-monotone linear tree linkages.'' Our goal is to find the maximum value of $k$ such that for fixed $k$, $k$-monotone linear tree linkages can always be unfolded. For this goal, we not only design efficient unfolding algorithms, but also search for locked instances. Finally, the most important result for this part is that we determine that the aforementioned maximum value of $k$ is exactly $4$.

並列關鍵字

Graph Optimization Algorithms ； Domination ； Independent Domination ； Edge-Independent Sets ； Geometric Unfolding Algorithms ； Minimal Locked Tree Linkages ； $k$-Monotone Linear Tree Linkages

參考文獻

[4] J. Alber, M. R. Fellows, and R. Niedermeier. Polynomial-time data reduction for dominating set. Journal of the ACM, 51(3):363–384, 2004.

[5] M. O. Albertson and K. L. Collins. Duality and perfection for edges in cliques. Journal of Combinatorial Theory, Series B, 36(3):298–309, 1984.

[6] L. Alcón, L. Faria, C. M. H. de Figueiredo, and M. Gutierrez. The complexity of clique graph recognition. Theoretical Computer Science, 410(21–23):2072–2083, 2009.

[7] P. Alimonti and T. Calamoneri. Improved approximations of independent dominating set in bounded degree graphs. In Proceedings of WG’96, pages 2–16, 1996.

[8] N. Alon and S. Gutner. Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica, 54(4):544–556, 2009.