[DMANET] Frontiers of Parameterized Complexity Resumes in 2021, first talk by Magnus Wahlstrom February 18

Dear all,

We are delighted to resume the Frontiers of Parameterized Complexity
talks from this week. For people hearing about it for the first time,
Frontiers of Parameterized Complexity has been an online talk series
since April 2020 concerning the latest topics in the area of
parameterized complexity. To get a glance of what has happened so far,
one can have a look at the list of previous talks
(https://frontpc.blogspot.com/2020/) and their video recordings at our
YouTube channel Frontiers of Paramerterized Complexity
(https://www.youtube.com/channel/UCdfML-PShQNSCeqbz9Ol_oA). 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.

The talks will be held every Thursday at 17:00 Bergen time (GMT+1). More
information about this can be found here https://frontpc.blogspot.com.
If you wish to get notifications of the talk announcements, please send
an email at rsharma@mpi-inf.mpg.de with the subject 'Subscribe FrontPC'
(if you are already subscribed to these notifications, please skip this
part).

Below are the details for joining the talk every Thursday at 17:00
Bergen time.
The link to join the zoom talk is https://uib.zoom.us/j/4231169675.

Meeting ID: 423 116 9675
Password: Name of the W[1]-complete problem, six letters, all capital.
Set of pairwise adjacent vertices.

Here are the details of this week's talk.

Date and Time: February 18, 2021 at 17:00 hours Bergen time (GMT+1)
Speaker: Magnus Wahlst\"orm, Royal Holloway University of London
Title: Quasipolynomial multicut-mimicking networks and kernelization of
multiway cut problems

Abstract: We show the existence of so-called mimicking networks of
k^O(log k) edges, mimicking the behaviour of multicuts over a set of
terminals of total capacity k. We also show an efficient (randomized)
construction that produces such a network with k^O(log^3 k) edges, using
an approximation algorithm for Small Set Expansion. This improves on a
recent result (W., ICALP 2020), which showed only the existence.

As a consequence, a range of problems have quasipolynomial kernels, in
particular including Edge Multiway Cut, Group Feedback Edge Set and
Subset Feedback Edge Set (in its general formulation, with undeletable
edges). The existence of a polynomial kernel for Multiway Cut is one of
the biggest open questions in kernelization, and this result is the
first improvement in general graphs since the introduction of the
representative sets approach to kernelization in 2012 (Kratsch and W.).

The talk assumes no previous knowledge of matroids or other previous
work on the problem.

--------------------------
Upcoming talks:

Date: February 25, 2021
Speaker: Bart Jansen, Eindhoven University of Technology
Title: Sparsification and CSP problems
Abstract: TBA

--------------------------

For any further questions, please contact one of the following.

Roohani Sharma, Max Planck Institute for Informatics:
rsharma@mpi-inf.mpg.de
Saket Saurabh, Institute of Mathematical Science, saket@imsc.res.in
Fedor Fomin, University of Bergen, fomin@ii.uib.no

--------------------------

Best regards
Roohani, Saket, Fedor
**********************************************************
*
* 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/
*
**********************************************************