# Noon lecture

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

On 26.5.2011 at 12:20 in S1, there is the following noon lecture:

# Feedback vertex set on graphs of low cliquewidth

## Ondøej Suchý

## Cluster of Excellence on "Multimodal Computing and Interaction", Universität des Saarlandes, Saarbrücken, Germany

## Abstract

The Feedback Vertex Set problem asks whether a graph contains q vertices meeting all its cycles. This is not a local property, in the sense that we cannot check if q vertices meet all cycles by looking only at their neighbors. Dynamic programming algorithms for problems based on non-local properties are usually more complicated. Here, given a graph G of cliquewidth cw and a cw-expression of G, we solve the Minimum Feedback Vertex Set problem in time $O(n^2 2^{O(cw \log cw)})$.

Our algorithm applies a non-standard dynamic programming on a so-called k-module decomposition of a graph, as defined by Rao [Disc. Math. 2008], which is easily derivable from a k-expression of the graph. The related notion of module-width of a graph is tightly linked to cliquewidth and we give an alternative equivalent

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

Webmaster: kamweb.mff.cuni.cz Archive page