Faster Exact and Approximate Algorithms for $k$-Cut
Preprint
Abstract
In the $k$-cut problem, we are given an edge-weighted graph $G$ and an integer $k$, and have to remove a set of edges with minimum total weight so that $G$ has at least $k$ connected components. The current best algorithms are an $O(n^{(2-o(1))k})$ randomized algorithm due to Karger and Stein, and an $\smash{\tilde{O}}(n^{2k})$ deterministic algorithm due to Thorup. Moreover, several $2$-approximation algorithms are known for the problem (due to Saran and Vazirani, Naor and Rabani, and Ravi and Sinha). It has remained an open problem to (a) improve the runtime of exact algorithms, and (b) to get better approximation algorithms. In this paper we show an $O(k^{O(k)} \, n^{(2\omega/3 + o(1))k})$-time algorithm for $k$-cut. Moreover, we show an $(1+\epsilon)$-approximation algorithm that runs in time $O((k/\epsilon)^{O(k)} \,n^{k + O(1)})$, and a $1.81$-approximation in fixed-parameter time $O(2^{O(k^2)}\,\text{poly}(n))$.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut ProblemAlgorithmica, 2009
- Approximating k-cuts using network strength as a Lagrangean relaxationEuropean Journal of Operational Research, 2008
- Parameterized Complexity and Approximation AlgorithmsThe Computer Journal, 2007
- A Deterministic Algorithm for Finding All Minimum k‐Way CutsSIAM Journal on Computing, 2007
- Approximating the Minimum k-way Cut in a Graph via Minimum 3-way CutsJournal of Combinatorial Optimization, 2001
- A fast algorithm for computing minimum 3-way and 4-way cutsMathematical Programming, 2000
- A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in GraphsJournal of Combinatorial Optimization, 2000
- A new and improved algorithm for the 3-cut problemOperations Research Letters, 1997
- Finding k Cuts within Twice the OptimalSIAM Journal on Computing, 1995
- Computing Edge-Connectivity in Multigraphs and Capacitated GraphsSIAM Journal on Discrete Mathematics, 1992