Feedback vertex set on graphs of low clique-width

The Feedback Vertex Set problem asks whether a graph contains qq vertices meeting all its cycles. This is not a local property, in the sense that we cannot check if qq vertices meet all cycles by looking only at their neighbors. Dynamic programming algorithms for problems based on non-local properties are usually more complicated. In this paper, given a graph GG of clique-width cwcw and a cwcw-expression of GG, we solve the Minimum Feedback Vertex Set problem in time O(n22O(cwlogcw))O(n22O(cwlogcw)). Our algorithm applies dynamic programming on a so-called kk-module decomposition of a graph, as defined by Rao (2008) [29], which is easily derivable from akk-expression of the graph. The related notion of module-width of a graph is tightly linked to both clique-width and NLC-width, and in this paper we give an alternative equivalent characterization of module-width.