IMSc Webinar

A Parameterized Approximation Scheme for Min k-Cut.

Saket Saurabh

IMSc

Webinar: Join at bluejeans.com/291474780/3489

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. 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 e>0, the algorithm obtains a (1+e)-approximate solution in time (k/e)^{O(k)} n^{O(1)}.

(This is a joint work with Daniel Lokshtanov, and Vaishali Surianarayanan).