Feedback vertex set

This problem was submitted by Ton Kloks, Department of Computer Science, Royal Holloway University of London, Egham, Surrey TW20OEX, UK

ton@cs.rhul.ac.uk

A feedback vertex set in a graph G is a set of vertices which meets all cycles of G. The FVS problem asks for a minimum cardinality feedback vertex set.

Problem 1: Given a planar graph G together with a tree decomposition of width k. Is there an algorithm solving the FVS problem for G and running in time O(c^k n) for some constant c?

Comment: An algorithm of running time O(k^k n) is known even for nonplanar graphs.
For plane graphs, a minimum cardinality set of vertices which meets every face can be found indeed in time O(c^k n).

Problem 2: A similar question can be asked for the problem of finding the maximum number of vertex disjoint cycles.

Back to the Problem Session page and to the workshop page