An 8-approximation algorithm for the subset feedback vertex set problem

We present an 8-approximation algorithm for the problem of finding a minimu m weight subset feedback vertex set ( or SUBSET-FVS, in short). The input i n this problem consists of an undirected graph G = (V, E) with vertex weigh ts c(v) and a subset of vertices S called special vertices. A cycle is call ed interesting if it contains at least one special vertex. A subset of vert ices is called a SUBSET-FVS with respect to S if it intersects every intere sting cycle. The goal is to nd a minimum weight SUBSET-FVS. The best previo us algorithm for the general case provided only a logarithmic approximation factor. The minimum weight SUBSET-FVS problem generalizes two NP-complete problems: the minimum weight feedback vertex set problem in undirected grap hs and the minimum weight multiway vertex cut problem. The main tool that w e use in our algorithm and its analysis is a new version of multicommodity ow, which we call relaxed multicommodity flow. Relaxed multicommodity ow is a hybrid of multicommodity ow and multiterminal flow.