[DMANET] Online Seminar on Frontiers of Parameterized Complexity: May 07, 2020 -- Jason Li

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 talk of the series will be held on May 07, 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: Jason Li, CMU
Title: Detecting Feedback Vertex Sets of Size k in O*(2.7^k) Time
Abstract: In the Feedback Vertex Set problem, one is given an
undirected graph $G$ and an integer $k$, and one needs to determine
whether there exists a set of $k$ vertices that intersects all cycles
of $G$ (a so-called feedback vertex set). Feedback Vertex Set is one
of the most central problems in parameterized complexity: It served as
an excellent test bed for many important algorithmic techniques in the
field such as Iterative Compression~[Guo et al. (JCSS'06)], Randomized
Branching~[Becker et al. (J. Artif. Intell. Res'00)] and
Cut\&Count~[Cygan et al. (FOCS'11)].

In particular, there has been a long race for the smallest dependence
$f(k)$ in run times of the type $O^\star(f(k))$, where the $O^\star$
notation omits factors polynomial in $n$. This race seemed to be run
in 2011, when a randomized $O^\star(3^k)$ time algorithm based on
Cut\&Count was introduced.

In this work, we show the contrary and give a $O^\star(2.7^k)$ time
randomized algorithm. Our algorithm combines all mentioned techniques
with substantial new ideas: First, we show that, given a feedback
vertex set of size $k$ of bounded average degree, a tree decomposition
of width $(1-\Omega(1))k$ can be found in polynomial time. Second, we
give a randomized branching strategy inspired by the one from~[Becker
et al. (J. Artif. Intell. Res'00)] to reduce to the aforementioned
bounded average degree setting. Third, we obtain significant run time
improvements by employing fast matrix multiplication.

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


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

May 21 2020:
Speaker: Micha\l Pilipczuk, University of Warsaw
Title: To be announced

May 28 2020:
Speaker: D\'aniel Marx, Max-Plack-Institut f\"ur Informatik
Title: To be announced

June 03 2020:
Speaker: Hans Bodlaender, Utrecht University
Title: Typical Sequences Revisited - Computing Width Parameters of Graphs


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