[DMANET] Online Seminar on Frontiers of Parameterized Complexity: April 30, 2020 -- Daniel Lokshtanov

We are excited to announce a new online seminar series on Frontiers of
Parameterized Complexity with talks scheduled weekly on Thursdays at
17.00 GMT+2 (Bergen time). Individuals and viewing party groups from
around the world can attend these online talks and interact with the
speaker and other attendees remotely via Zoom.

More details about the seminar series can be found here:
https://frontpc.blogspot.com/2020/04/talks-schedule.html

The (next) second talk of the series 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.


********************************************************
Other upcoming talks in the series include:

May 07 2020:
Speaker: Jason Li, CMU
Title: To be announced

May 14 2020:
Speaker: Vincent Cohen-Addad, Google Z\"urich
Title: On the Parameterized Complexity of Various Clustering Problems

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/
*
**********************************************************