二元圖上星狀生成樹林之研究

A Study of the Spanning Star Forest Problem on Bipartite Graphs

林晏禕(Yen-Yi Lin)

指導教授 ： 趙坤茂

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.00064

摘要

我們在本篇論文中主要探討星狀生成樹林問題，以及其在二元圖上的相關結果。星狀生成樹林與控制集的關係不但易於了解，並且能夠快速轉換。雖然要找到這兩個問題的最佳解皆屬 NP-Hard, 但我們希望能夠憑藉著圖論學家在控制集上的豐碩成果，對星狀生成樹林做出進一步的探索。由於圖論學家多半探討的是控制集的大小，因此我們希望能藉由在計算複雜度與演算法效率上的分析對這個問題做出貢獻。

近來在生物資訊領域中，演化樹建構成為重要的探討主題。由於兩兩序列比對問題相較多重序列比對問題更易找出最佳解，某些軟體期望能藉由合併物種間兩兩比對的結果快速建出所有物種的演化樹。然而在序列重複區域極多的情形下，這些軟體往往會耗費很多空間，在最糟的狀況下甚至是以物種數的指數倍速度成長。為了解決這個問題， 2007 年 Nguyen et al. 提出了一套方法；倘若我們在建構演化樹過程中能以此方法建模，將比對結果轉化成二元圖，那麼該圖上夠大的星狀生成樹林能協助我們僅以線性的空間便找到理想的演化樹雛型。這使得二元樹上星狀生成樹林的問題再度吸引眾人的目光。

本篇論文中，我們首先證明星狀生成樹林在二元圖上的最佳化問題不但是 NP-Hard, 而且除非 NP = P, 否則此問題將有逼近比例的上限。接著，我們給出了一個在多項式時間內，對多數二元圖皆可找到 0.67 逼近比例生成樹林的演算法。

關鍵字

組合最佳化 ； 近似演算法 ； 二元圖 ； 星狀生成樹林 ； 控制集

並列摘要

We study the spanning star forest problem (SSF) and its variation on bipartite graphs (BSSF). The relation between SSF and the dominating set problem (DOM), which has fruitful results in the literature, has been observed. The related optimization problems MSSF and MBSSF are of NP-Hard in general, and we hope to contribute to the issues by concentrating on theoretical aspects of approximation algorithms and combinatorial optimization.

In this thesis we demonstrate a general framework for approximating MBSSF based on available results of the dominating set problem. We hope to solve this problem by the upper bounds of the domination number. Based on several available domination numbers with constraints, we devise a polynomial time algorithm which obtains a 0.67 approximation ratio for most instances. We also construct some combinatorial witness of such a dominating set efficiently. By extending the dominating set to corresponding spanning star forest, we claim to have efficient algorithms for MBSSF.

並列關鍵字

combinatorial optimization ； approximation algorithms ； bipartite graph ； spanning star forest ； dominating set

參考文獻

[4] N. Chen, R. Engelberg, C. Nguyen, P. Raghavendra, A. Rudra, and G. Singh.

[10] M. X. Goemans and D. P. Williamson. A general approximation technique

[11] T. W. Haynes, S. Hedetniemi, and P. Slater. Fundamentals of Dom-

[2] G. J. Chang and G. L. Nemhauser. The k-domination and k-

[3] K. Chao and L. Zhang. Sequence Comparison: Theory and Meth-