Abstract
In an undirected graph, a kcut is a set of edges whose removal breaks the graph into at least k connected components. The minimum weight kcut can be computed in n^O(k) time, but when k is treated as part of the input, computing the minimum weight kcut is NPHard [Goldschmidt and Hochbaum, 1994]. For poly(m,n,k)time algorithms, the best possible approximation factor is essentially 2 under the small set expansion hypothesis [Manurangsi, 2017]. Saran and Vazirani [1995] showed that a (2  2/k)approximately minimum weight kcut can be computed via O(k) minimum cuts, which implies a O~(km) randomized running time via the nearly linear time randomized mincut algorithm of Karger [2000]. Nagamochi and Kamidoi [2007] showed that a (2  2/k)approximately minimum weight kcut can be computed deterministically in O(mn + n^2 log n) time. These results prompt two basic questions. The first concerns the role of randomization. Is there a deterministic algorithm for 2approximate kcuts matching the randomized running time of O~(km)? The second question qualitatively compares minimum cut to 2approximate minimum kcut. Can 2approximate kcuts be computed as fast as the minimum cut  in O~(m) randomized time?
We give a deterministic approximation algorithm that computes (2 + eps)minimum kcuts in O(m log^3 n / eps^2) time, via a (1 + eps)approximation for an LP relaxation of kcut.
BibTeX  Entry
@InProceedings{quanrud:LIPIcs:2019:11238,
author = {Kent Quanrud},
title = {{Fast and Deterministic Approximations for kCut}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {23:123:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11238},
URN = {urn:nbn:de:0030drops112388},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.23},
annote = {Keywords: kcut, multiplicative weight updates}
}
Keywords: 

kcut, multiplicative weight updates 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) 
Issue Date: 

2019 
Date of publication: 

17.09.2019 