# Removing all but a few cycles in a graph

Let problem $S$ be defined as

Given undirected graph $G$ and a set of cycles $C_1,C_2, \ldots, C_n$ in G, find minimum number of vertices that need to be deleted to remove all cycles in the graph G except the specified set.

Surely Problem $S$ is NP-hard, since finding minimum number of vertices required to remove all cycles in G (feedback vertex set) is NP-hard

My question is:

Is it possible to Reduce Problem S to the feedback vertex set problem in an undirected or directed graph reduction such that if there exist a solution for problem S of size at most k in G iff there exist a feedback vertex set of size at most k in G'

ksoltys gives a reduction (answer below) from Problem S to feedback vertex set when we are not allowed to pick vertices from the forbidden cycles $C_1,C_2, \ldots, C_n$ .Suppose we are allowed to pick vertices from these forbidden cycle. Is there a reduction such that if there exist a solution for problem S of size at most k in G iff there exist a feedback vertex set of size at most k in G'

• please note the edits to the text. In the future, it would be helpful to format your questions in this manner. – Suresh Venkat Sep 13 '10 at 8:21
• Could you perhaps provide some further background information. What kind of reduction are you looking for and why? Do you have a feedback vertex set solver that you would like to apply here (which solver, and why would you like to use it)? Is it an approximation algorithm; should the reduction preserve the approximation ratio, etc.? – Jukka Suomela Sep 13 '10 at 8:53
• Must the cycles $C_1, \dots, C_n$ be left intact? Are we allowed to break these cycles? – Emil Sep 13 '10 at 10:19
• @Daniel Apon: I do not think so. Let G be the complete graph on four vertices and C be a triangle in G. Then G∖C does not contain a cycle, but you have to remove one vertex to break all cycles in G but C. – Tsuyoshi Ito Sep 13 '10 at 12:03
• Does that mean that you want a reduction which does not change the threshold value k? If so, I think that you should state that in the question, because it is pretty different from just having a reduction. – Tsuyoshi Ito Sep 14 '10 at 11:21

I think I have such a reduction for the case when we aren't allowed to break the given cycles. Let $C$ be the set of the vertices belonging to the selected cycles (wlog assume that $G[C]$ is connected), and let $D = V\setminus C$. We cannot remove any vertex from $C$. Let's collapse all the vertices from $C$ into one vertex $c_1$ (of course delete the created loops, but keep the double edges), and create $k$ copies of $c$, with the same neighborhood (so now we have a graph on $\{c_1, \dots, c_{k+1}\} \cup D$). We now search for a feedback vertex set. If I'm not mistaken, instance of feedback vertex set thus created has a solution of size $k$ iff our graph had a solution of size $k$ to our problem.

edit: Answer to Prabu's doubt from the comment

The vertices $v_1$ and $v_4$ would indeed collapse to a vertex $v$ (with all other vertices of the forbidden cycles), but the reduction creates $k+1$ copies of $v$ (let's call them $w_1, ..., w_{k+1}$). So the cycle $P$ is transformed into two families of cycles: $F_1 = \{(w_i, v_2, v_3, w_i): i \in [k+1]\}$ and $F_2 = \{(w_i, v_5, v_6, w_i): i \in [k+1]\}$. To break all the cycles from $F_1$, we would have to delete either all the vertices $w_i$ (but we can't, there's too many of them), or one of the vertices $\{v_2, v_3\}$. Same goes for $F_2$ - so altogether we delete exactly 2 vertices.

Let's now look at our original graph. We have two cycles here, one is $P$, and the other: $(v_1, v_2, v_3, v_4, c_1, c_2, ..., c_l, v_1)$, where $v_4, c_1, ..., c_l, v_1$ is some path from $v_4$ to $v_1$ using only the vertices from the forbidden cycles, which we cannot delete (we assumed that $G[C]$ is connected, if we want to get rid of this assumption, we would have to consider connected components of $C$ and collapse vertices from these components separately). To destroy both of this cycles we would also have to delete one vertex from $\{v_2, v_3\}$ and one from $\{v_5, v_6\}$ (you can easily see this when you draw this graph).

So the reduction did exactly what we wanted in this case.

• I have a doubt here. Consider a cycle $P$ say $v_1,v_2 \ldots,v_6$ which is not in specified cycles $C_1,C2 \ldots, C_n$ and let $P \cup C1 =v_1$ and $P \cup C2 =v_4$ and all other cycles $C_i \cup P = \NULL$ where i =3 $\ldots$k . Now after collapsing $v_{1}$ and $v_{4}$ to v . How will P cycle look. – Prabu Oct 6 '10 at 7:00
• sorry $\emptyset$ is misspelled as $\NULL$ and i =3 $\ldots$ n not k. i could not edit back – Prabu Oct 6 '10 at 7:09
• so we got two cycles $c_1 (v_1,v_2,v_3,v_4,c_1,c_2\ldots,c_l,v_1$ and $c_1 (v_1,v_6,v_5,c_1,c_2\ldots,c_l,v_1$. so we are force to remove the two vertices . – Prabu Oct 7 '10 at 5:43
• @karolina I do not get it why there should be a path from $v_{1}$ to $v_{4}$ through the forbidden cycle. – Prabu Oct 7 '10 at 5:48
• every connected component of C is collapsed into $v_1,v_2 \ldots,v_n$ and then for every $v_i$ k+1 copies are produced.i got it. Thanks. – Prabu Oct 7 '10 at 9:25