叢集圖編修問題的固定參數演算法

Parameterized Algorithms for Cluster-Graph Modification Problems

陳立軒(Li-Hsuan Chen)

指導教授 ： 張貿翔 ； 吳邦一

國立中正大學/工學院/資訊工程學系/博士(2016年)

摘要

叢集圖編修問題是資訊科學的一個重要問题。一般來說，此問題可理解為給定了一個點之間連線代表相似物件的圖，要求把相似物件分群。在理論研究中，此問題被建構為用最少的編修把輸入的圖編修成叢集圖。由於此問題的應用廣泛，最少編修的定義有許多不同的建構方式。在本論文中，我們展示了一些解決各種叢集圖編修問題的參數化演算法。

二分群問題一般來說是要求把圖分成兩群，群內的點之間沒邊的數量及群之間的邊數要越小越好。針對最常用的目標函數：最小總和、最小平方和、以及最大值最小，我們設計了數個演算法來解決這些最佳化問題。
至於p分群問題則要求把圖分成p個叢集，我們發展了一些方法利用額外的參數p來得到更好的結果。在p分群問題上，我們也研究了刪除點的版本並設計了有效率的多參數演算法。

關鍵字

隨機演算法 ； 分群 ； 叢集圖編修 ； 固定參數複雜度 ； 參數化演算法 ； 次指數演算法

並列摘要

emph{Graph clustering} is an important issue in computer science. In general, we are given a graph with edges between similar objects, and the goal is to group the similar objects into clusters. A theoretical approach asks for editing a graph into disjoint cliques. Due to the wide applications, there are many formulated problem definitions. In this study, we show parameterized algorithms for some of the graph modification problems.

A 2-clustering problem in general asks for a 2-partition such that the number of edges between the 2-partition and the non-edges in the same partition are as ``small'' as possible. As in many optimization problems, we developed several algorithms for the most frequently used cost functions: min-sum, min-max, and min-sum of squares.

For the $p$-clusterings problems, in which the vertex set is split into $p$ clusters, we developed some ways to make use of the additional parameter $p$ to obtain better results with multiple parameters. We study the vertex deletion version and design an efficient algorithm with multiple parameters.

並列關鍵字

randomized algorithms ； clustering ； graph modification ； fixed-parameter complexity ； parameterized algorithm ； subexponential algorithms

參考文獻

[1] F. N. Abu-Khzam, A kernelization algorithm for d-hitting set," Journal of Computer and System Sciences, vol. 76, no. 7, pp. 524-531, 2010.

[4] S. Bocker, S. Briesemeister, Q. Bui, and A. Truss, Going weighted: Parameterized algorithms for cluster editing," Theoretical Computer Science, vol. 410, no. 52, pp. 5467-5480, 2009.

[5] S. Bocker and P. Damaschke, Even faster parameterized cluster deletion and cluster editing," Information Processing Letters, vol. 111, no. 14, pp. 717-721, 2011.

[6] S. Bcker, A golden ratio parameterized algorithm for cluster editing," Journal of Discrete Algorithms, vol. 16, pp. 79-89, 2012. Selected papers from the 22nd International Workshop on Combinatorial Algorithms (IWOCA 2011).

[7] P. Bonizzoni, G. D. Vedova, R. Dondi, and T. Jiang, On the approximation of correlation clustering and consensus clustering," Journal of Computer and System Sciences, vol. 74, no. 5, pp. 671-696, 2008.