[DMANET] Reminder: Next talk in Frontiers of Parameterized Complexity on May 07, 2020 by Jason Li

This is a reminder for this week's talk in the ongoing 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 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.

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