A Deterministic Algorithm for Finding All Minimum <i>k</i>‐Way Cuts

Abstract

Let $G=(V,E)$ be an edge‐weighted undirected graph with n vertices and m edges. We present a deterministic algorithm to compute a minimum k‐way cut of G for a given k. Our algorithm is a divide‐and‐conquer method based on a procedure that reduces an instance of the minimum k‐way cut problem to $O(n^{2k-5})$ instances of the minimum $(\lfloor (k+\sqrt{k})/2\rfloor+1)$‐way cut problem, and can be implemented to run in $O(n^{4k/(1-1.71/\sqrt{k}) -31} )$ time. With a slight modification, the algorithm can find all minimum k‐way cuts in $O(n^{4k/(1-1.71/\sqrt{k}) -16} )$ time.