Adversarial queueing theory
Allan Borodin, Jon Kleinberg, et al.
STOC 1996
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 the graph bipartization problem, in winch one must remove a minimum-weight set of vertices so that the remaining graph is bipartite. We give a 9/4-approximation algorithm for the general problem in planar graphs, given that the subset of cycles obeys certain properties. This results in 9/4-approximation algorithms for the aforementioned feedback and bipartization problems in planar graphs. Our algorithms use the primal-dual method for approximation algorithms as given in Goemans and Williamson [16]. We also show that our results have an interesting bearing on a conjecture of Akiyama and Watanabe [2] on the cardinality of feedback vertex sets in planar graphs.
Allan Borodin, Jon Kleinberg, et al.
STOC 1996
Andreas S. Schulz, David B. Shmoys, et al.
PNAS
Monika Henzinger, David P. Williamson
Information Processing Letters
Ronald Fagin, Ravi Kumar, et al.
WWW 2003