Ondra Suchy (Universität des Saarlandes)

This talk is especially suitable for those not familiar with
clique-width and willing to understand what is it all about. We use a
non-standard dynamic programming on a so-called k-module decomposition
of a graph to solve the Feedback Vertex Set problem, which 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 clique-width 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)}).

This is a joint work with B.-M. Bui-Xuan, J. A. Telle, and M. Vatshelle.

Back to the research colloquium site.