A PARAMETERIZED APPROXIMATION SCHEME FOR MIN k-CUT.

In the Min k-Cut problem, the input consists of an edge weighted graph G and an integer k, and the task is to partition the vertex set into k nonempty 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, Lee, and Li [Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, A. Czumaj, ed., SIAM, Philadelphia, 2018, pp. 2821--2837] initiated the study of FPT-approximation for the Min k-Cut problem and gave a 1.9997-approximation algorithm running in time 2\scrO (k6)n\scrO (1). Later, the same set of authors [Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, M. Thorup, ed., 2018, pp. 113--123] designed a (1 + \epsilon)-approximation algorithm that runs in time (k/\epsilon)\scrO (k)nk+\scrO (1) and a 1.81-approximation algorithm running in time 2\scrO (k2)n\scrO (1). More, recently, Kawarabayashi and Lin [Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms, S. Chawla, ed., SIAM, Philadelphia, 2020, pp. 990--999] gave a (5/3+\epsilon)-approximation for Min k-Cut running in time 2\scrO (k2 log k)n\scrO (1). 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 the exponential time hypothesis and constants in the exponent). In particular, for every \epsilon > 0, the algorithm obtains a (1 + \epsilon)-approximate solution in time (k/\epsilon)\scrO (k)n\scrO (1). 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\scrO (k)n\scrO (1) on unweighted (multi-) graphs. Here, s denotes the number of edges in a minimum k-cut. The latter two are of independent interest. [ABSTRACT FROM AUTHOR]