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.