[DMANET] Reminder: Next talk in Frontiers of Parameterized Complexity on April 30, 2020 by Daniel Lokshtanov

This is a reminder for this week's talk in the newly launched online
seminar series on Frontiers of Parameterized Complexity. More details
about the seminar series can be found here:
https://frontpc.blogspot.com/2020/04/talks-schedule.html

This week's talk will be held on April 30, 2020 at 17:00 GMT+2.

The link to join the meeting on Zoom is https://uib.zoom.us/j/4231169675
Meeting ID: 423 116 9675
Password: Name of the W[1]-complete problem, 6 letters, all capital.
Also known as a set of pairwise adjacent vertices.

Speaker: Daniel Lokshtanov, UCSB
Title: A Parameterized Approximation Scheme for Min k-Cut
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 {\em 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^{O(k^6}n^{O(1)}. Later, the same set of authors~[FOCS 2018]
designed an (1 +\epsilon)-approximation algorithm that runs in time
(k/\epsilon)^{O(k)}n^{k+O(1)}, and a 1.81-approximation algorithm
running in time 2^{O(k^2)}n^{O(1)}. More, recently, Kawarabayashi and
Lin~[SODA 2020] gave a (5/3 + \epsilon)-approximation for Min k-Cut
running in time 2^{O(k^2 \log k)}n^{O(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 Exponential Time Hypothesis (\ETH)
and constants in the exponent). In particular, for every \epsilon > 0,
the algorithm obtains a (1 +\epsilon)-approximate solution in time
(k/\epsilon)^{O(k)}n^{O(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^{O(k)}n^{O(1)} on unweighted
(multi-) graphs. Here, s denotes the number of edges in a minimum
k-cut. The later two are of independent interest.

For more details please contact one of the following.

Roohani Sharma: roohani@imsc.res.in
Saket Saurabh: saket@imsc.res.in
Fedor Fomin: Fedor.Fomin@uib.no

Best regards and cheers!


**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************