Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | future lectures)

On 19.03.2019 at 12:30 in S10, there is the following noon lecture:

Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set

Matthias Mnich

Abstract

The Directed Feedback Vertex Set (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp's 21 NP-complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. in 2008 showed its fixed-parameter tractability via a 4^k k! n^{O(1)}-time algorithm, where k = |S|.

We show fixed-parameter tractability of two generalizations of DFVS:

- Find a smallest vertex set S such that every strong component of G-S has size at most s: we give an algorithm solving this problem in time 4^k (ks + k + s)! n^{O(1)}.

- Find a smallest vertex set S such that every non-trivial strong component of G-S is 1-out-regular: we give an algorithm solving this problem in time 2^{O(k^3)}n^{O(1)}. We also solve the corresponding arc versions of these problems by fixed-parameter algorithms.

(joint work with Alexander Göke and Dániel Marx)

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 25. 02. 2019