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.