Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #99018 (October, 1999)

A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs
by Hiroshi Nagamochi, Shigeki Katayama and Toshihide Ibaraki

For an edge-weighted graph $G$ with $n$ vertices and $m$ edges, the minimum $k$-way cut problem is to find a partition of the vertex set into $k$ non-empty subsets so that the weight sum of edges between different subsets is minimized. For this problem with $k=5$ and $6$, we present a deterministic algorithm that runs in $O(n^{k-2}(nF(n,m)+C_2(n,m)+n^2))=O(mn^{k}\log (n^2/m))$ time, where $F(n,m)$ and $C_2(n,m)$ denote respectively the time bounds required to solve the maximum flow problem and the minimum 2-way cut problem in $G$. The bounds $\tilde{O}(mn^5)$ for $k=5$ and $\tilde{O}(mn^6)$ for $k=6$ improve the previous best %deterministic bound $\tilde{O}(mn^5)$ and randomized bounds $\tilde{O}(n^8)$ and $\tilde{O}(n^{10})$, respectively.