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