Given an undirected graph G=(V,E) with nonnegative weights on the
vertices, the feedback vertex set problem is that of finding a
minimum-weight set T of vertices such that every cycle of the graph
contains a vertex in T. Several variants of this problem have been
studied, including those in which one must find a minimum-weight set
of vertices T such that: (1) every directed cycle of a directed graph
contains a vertex in T (the directed feedback vertex set problem); (2)
every odd length cycle contains a vertex of T (the graph bipartization
problem); (3) every cycle containing a vertex of a given set S
contains a vertex of T (the subset feedback vertex set problem). All
of these problems are NP-hard, even in planar graphs. In this talk,
we show how the primal-dual method for approximation algorithms can be
used to find a solution of value within 9/4 times the value of an
optimal solution for each of these problems in the case of planar
graphs.
Joint work with Michel Goemans.