TY - GEN

T1 - Faster exact and approximate algorithms for k-cut

AU - Gupta, Anupam

AU - Lee, Euiwoong

AU - Li, Jason

N1 - Publisher Copyright:
© 2018 IEEE.

PY - 2018/11/30

Y1 - 2018/11/30

N2 - 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 Õ(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ω/3+o(1))k )-time algorithm for k-CUT. Moreover, we show an (1 + ϵ)-approximation algorithm that runs in time O((k/ϵ) O(k) n k+O(1) ), and a 1.81-approximation in fixed-parameter time O(2 O(k) poly(n)).

AB - 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 Õ(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ω/3+o(1))k )-time algorithm for k-CUT. Moreover, we show an (1 + ϵ)-approximation algorithm that runs in time O((k/ϵ) O(k) n k+O(1) ), and a 1.81-approximation in fixed-parameter time O(2 O(k) poly(n)).

KW - Approximation algorithms

KW - Graph algorithms

KW - Minimum k-cut

KW - Parameterized algorithm

UR - http://www.scopus.com/inward/record.url?scp=85059803448&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85059803448&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2018.00020

DO - 10.1109/FOCS.2018.00020

M3 - Conference contribution

AN - SCOPUS:85059803448

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 113

EP - 123

BT - Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018

A2 - Thorup, Mikkel

PB - IEEE Computer Society

T2 - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018

Y2 - 7 October 2018 through 9 October 2018

ER -