A Parameterized Approximation Scheme for Min $k$-Cut
Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan
Abstract
In the Min k-cut problem, input is an edge weighted graph G and an integer k, and the task is to partition the vertex set into k non-empty sets, such that the total weight of the edges with endpoints in different parts is minimized. When k is part of the input, the problem is NP-complete and hard to approximate within any factor less than 2. Recently, the problem has received significant attention from the perspective of parameterized approximation. Gupta et al. [SODA 2018] initiated the study of FPT-approximation for the Min k-Cut problem and gave an 1.9997-approximation algorithm running in time 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(k6</sup> )n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1)</sup> . Later, the same set of authors [FOCS 2018] designed an ( 1+ε)-approximation algorithm that runs in time (k/ε) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(k)</sup> n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k+O(1)</sup> , and a 1.81-approximation algorithm running in time 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(k2</sup> )n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1)</sup> . More, recently, Kawarabayashi and Lin [SODA 2020] gave a (5/3+ε)-approximation for Min k-Cut running in time 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(k2</sup> logk)n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1)</sup> . In this paper we give a parameterized approximation algorithm with best possible approximation guarantee, and best possible running time dependence on said guarantee (up to Exponential Time Hypothesis (ETH) and constants in the exponent). In particular, for every , the algorithm obtains a ( 1+ε)-approximate solution in time (k/ε) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(k)</sup> n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1)</sup> . The main ingredients of our algorithm are: a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time s <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(k)</sup> n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1)</sup> on unweighted (multi-) graphs. Here, s denotes the number of edges in a minimum k-cut. The latter two are of independent interest.