Improved Algorithms for the Cut Enumeration Problem and the Minimum k-cut Problem

列舉分割問題及最小 k 分割問題之改進演算法

葉立璞(Li-Pu Yeh)

指導教授 ： 王炳豐

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

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

摘要

在本論文中，我們討論列舉分割問題及最小 k 分割問題。對於列舉分割問題，在1992年，Vazirani 和 Yannakakis 提出了一個演算法，在兩個輸出之間的時間延遲為 Õ(n^2m) ， Õ(f) 表示 O(flog^c f) ， c 為一個常數。我們提出了一個改進演算法，在兩個輸出之間的延遲為 Õ(nm)。 Vazirani 和 Yannakakis 的演算法在很多其他的問題中被當成副程序使用。因此，我們的演算法也同時改進了這些問題的時間複雜度。對於最小 k 分割問題，我們利用 divide-and-conquer 提出了兩個新的方法。令 T(k) 為找尋一個最小 k 分割的時間複雜度。第一個方法把一個最小 k 分割問題轉換成 O(2^(k-1)kn^3) 個最小 k-1 分割問題。因此，我們得到 T(k) = O(2^(k-1)kn^3T(k-1))。在k = 7, 8, 9, 10 時，這個方法比過去的演算法好，時間複雜度下降 O(n^(11-k))。做一些修改後，這個方法也可以在 O(n^(3k-6)mlog (n^2/m)) 時間內找出所有的最小 k 分割。當 k = 3 時，我們的方法讓時間複雜度下降 O(n)。第二個方法把一個最小 k 分割問題轉換成 O(n^(2floor(k/2))m) 個最小 ceiling(k/2) 分割問題。因此，我們得到 T(k) = Õ(n^(2floor(k/2))mT(ceiling(k/2))。當 10 <= k <= 28，這個方法改進了之前最好的結果。舉例來說，在k = 10, 11, 12時，我們的演算法讓時間複雜度各下降 O(n^4/m), O(n^5/m), O(n^5/m)。

關鍵字

演算法 ； 圖 ； 最大流量 ； 最小分割 ； 列舉問題 ； k 分割 ； 次佳分割

並列摘要

In this dissertation, we study the cut enumeration problem and the minimum k-cut problem. For the cut enumeration problem, an efficient algorithm with Õ(n^2m) delay between two successive outputs has been known since 1992, due to Vazirani and Yannakakis, where Õ(f) denotes O(flog^c f) for some constant c. In this dissertation, an improved algorithm is presented. The delay of the presented algorithm is Õ(nm). Vazirani and Yannakakis's algorithm has been used as a basic subroutine in the solutions of many problems. Therefore, our improvement immediately reduces the running time of these solutions. For the minimum k-cut problem, two new divide-and-conquer approaches are presented. Let T(k) denote the time complexity of finding a minimum k-cut. The first one reduces an instance of the minimum k-cut problem to O(2^(k-1)kn^3) instances of the minimum (k-1)-cut problem. Thus, our first approach shows that T(k) = O(2^(k-1)kn^3T(k-1)). For k = 7, 8, 9, 10, this approach improves the previous upper bound by a factor of O(n^(11-k)). With some modifications, the approach can also find all minimum k-cuts in O(n^(3k-6)mlog (n^2/m)) time for any constant k >= 3. When k = 3, this result improves the previous upper bound for finding all minimum 3-cuts from Õ(n^4m) to Õ(n^3m). Our second approach reduces an instance of the minimum k-cut problem to O(n^(2*floor(k/2))m) instances of the minimum (ceiling(k/2))-cut problem. Thus, our second approach shows that T(k) = Õ(n^(2*floor(k/2))mT(ceiling(k/2))). For 10 <= k <= 28, this approach is more efficient than the previous upper bound. For example, for k = 10, 11, and 12, we improve the upper bound by a factor of O(n^4/m), O(n^5/m), and O(n^5/m), respectively.

並列關鍵字

algorithms ； graphs ； maximum flows ； minimum cuts ； enumeration ； k-cuts ； suboptimal cuts

參考文獻

[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1st ed., 1993.

[2] S. Arora, S. Rao, and U. V. Vazirani, "Expander flows, geometric embeddings and graph partitioning," in 36th ACM Symposium on Theory of Computing (STOC 2004), pp. 222-231, 2004.

[3] M. Burlet and O. Goldschmidt, "A new and improved algorithm for the 3-cut problem," Operations Research Letters, vol. 21, pp. 225-227, 1997.

[4] G. Cãlinescu, H. Karloff, and Y. Rabani, "An improved approximation algorithm for multiway cut," J. Comput. Syst. Sci., Vol. 60, pp. 564-574, 2000.

[6] D.Z. Chen and X. Wu, "Efficient algorithms for k-terminal cuts on planar graphs," Lecture Notes Computer Science, Vol. 2223, pp. 332-344, 2001.