×

Primal-dual approximation algorithms for feedback problems in planar graphs. (English) Zbl 0928.90094

Summary: Given a subset of cycles of a graph, we consider the problem of finding a minimum-weight set of vertices that meets all cycles in the subset. This problem generalizes a number of problems, including the minimum-weight feedback vertex set problem in both directed and undirected graphs, the subset feedback vertex set problem, and graph bipartization problem, in which one must remove a minimum-weight set of vetrices so that the remaining graph is bipartite. We give a \(\frac 94\)-approximation algorithm for the general problem in planar graphs, given that the subset of cycles obeys certain properties. This results in \(\frac 94\)-approximation algorithms for the aforementioned feedback and bipartization problems in planar graphs. We also show that our results have an interesting bearing on a conjecture of Akiyama and Watanabe on the cardinality of feedback vertex sets in planar graphs.

MSC:

90C35 Programming involving graphs or networks
68Q25 Analysis of algorithms and problem complexity
05C85 Graph algorithms (graph-theoretic aspects)
90C27 Combinatorial optimization
Full Text: DOI