<p>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.</p>

<p><strong>edit:</strong> Answer to Prabu's doubt from the comment</p>

<p>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.</p>

<p>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).</p>

<p>So the reduction did exactly what we wanted in this case.</p>

CC BY-SA 2.5
2010-10-06T07:00:38.043Z
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 
CC BY-SA 2.5
2010-10-06T07:09:36.070Z
sorry $\emptyset$ is misspelled as $\NULL$ and  i =3 $\ldots$ n not k. i could not edit back
Prabu 
CC BY-SA 2.5
2010-10-07T05:43:37.387Z
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 
CC BY-SA 2.5
2010-10-07T05:48:33.710Z
@karolina I do not get it why there should be a path from $v_{1}$ to $v_{4}$ through the forbidden cycle.
Prabu 
CC BY-SA 2.5
2010-10-07T09:25:59.113Z
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 
CC BY-SA 2.5
2010-10-07T09:41:53.253Z
is it possible to have a similar kind of reduction when we are allowed to break these cycles.
Prabu 
CC BY-SA 2.5
2010-10-05T18:42:22.207Z
2010-10-06T21:33:56.670Z
2010-10-06T21:33:56.670Z
Karolina Sołtys
<p>Let problem $S$ be defined as</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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</p>

<p>My question is:</p>

<blockquote>
  <p>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'</p>
</blockquote>

<p>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'</p>

CC BY-SA 2.5
2010-09-13T08:21:56.543Z
please note the edits to the text. In the future, it would be helpful to format your questions in this manner.
Suresh Venkat
CC BY-SA 2.5
2010-09-13T08:53:02.343Z
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
CC BY-SA 2.5
2010-09-13T09:36:30.917Z
Wouldn't solving feedback vertex set on $G\backslash C_1,C_2,...,C_n$ solve $S$?
Daniel Apon
CC BY-SA 2.5
2010-09-13T10:19:49.170Z
Must the cycles $C_1, \dots, C_n$ be left intact? Are we allowed to break these cycles?
Emil
CC BY-SA 2.5
2010-09-13T12:03:52.240Z
@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
CC BY-SA 2.5
2010-09-13T13:08:35.187Z
I do not think that you stated the question you wanted to ask correctly.  Since the decision version of the problem S (is it possible to remove all cycles but given ones by deleting at most k vertices?) is in NP and the decision version of the Feedback Vertex Set is NP-complete, it is of course _possible_ to reduce the problem S to the Feedback Vertex Set by a Turing reduction.  You may want to ask for a better reduction than this, but to do so, you have to specify _better_ in which sense.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-13T17:53:17.453Z
@jukka  I need a polynomial reduction to the problem s to Feedback vertex ,so that i can use approximation algorithm of feedback vertex set problem or to $k^2$ Kernelization of feedback vertex set in decision problem
Prabu 
CC BY-SA 2.5
2010-09-13T17:58:30.843Z
@Tsuyoshi Example is correct but i want a polynomial reduction directly from s to feedback vertex set.
Prabu 
CC BY-SA 2.5
2010-09-13T19:56:53.570Z
You can always construct a “direct” reduction by composing several reductions.  This is why I think you did not state the question correctly.  To state a question, you have to put some effort to clarify what you really want to know.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-14T08:15:49.013Z
i want a reduction from problem S to feedback vertex set 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'
Prabu 
CC BY-SA 2.5
2010-09-14T11:21:59.220Z
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
CC BY-SA 2.5
2010-09-14T17:13:00.393Z
RE: My earlier comment, Tsuyoshi's response, and Emil's question: Let G be the complete graph on four vertices, let C be the "box" cycle that connects all four vertices. In this case, you cannot remove any of the triangle cycles unless you break C as well. What would the correct answer to S be in this case? 0? No correct answer? This makes me believe S needs to be re-worded a tad...
Daniel Apon
CC BY-SA 2.5
2010-09-16T00:29:51.240Z
@Daniel: My interpretation of the problem S was that you can break any of the given cycles if you want to.  If this is what the questioner’s intent, the answer to your case is 2 because you have to remove the four triangles anyway.  But of course I do not know what the questioner’s intent really is.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-16T06:47:10.340Z
@Daniel your question does not have answer as all vertices of all cycles are connected to C
Prabu 
CC BY-SA 2.5
2010-09-16T06:48:01.403Z
@Tsuyoshi we are not allowed to break the cycles
Prabu 
CC BY-SA 2.5
2010-09-16T07:00:03.630Z
@Tsuyoshi If u have reduction assuming that cycle $C$ can be allowed to break. please post your idea.
Prabu 
CC BY-SA 2.5
2010-09-16T07:50:29.257Z
I do not have a reduction with the stated property under either interpretation.
Tsuyoshi Ito
<cc.complexity-theory><graph-theory><np-hardness><reductions>
Removing all but a few cycles in a graph
Prabu 
# Removing all but a few cycles in a graph

(Asked by: username_0 on 2010-09-13)

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'

**Tags:** cc.complexity-theory, graph-theory, np-hardness, reductions
> **Comments:**
> **username_1**: please note the edits to the text. In the future, it would be helpful to format your questions in this manner.  
> **username_2**: 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.?  
> **username_3**: Wouldn't solving feedback vertex set on $G\backslash C_1,C_2,...,C_n$ solve $S$?  
> **username_4**: Must the cycles $C_1, \dots, C_n$ be left intact? Are we allowed to break these cycles?  
> **username_5**: @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.  
> **username_5**: I do not think that you stated the question you wanted to ask correctly.  Since the decision version of the problem S (is it possible to remove all cycles but given ones by deleting at most k vertices?) is in NP and the decision version of the Feedback Vertex Set is NP-complete, it is of course _possible_ to reduce the problem S to the Feedback Vertex Set by a Turing reduction.  You may want to ask for a better reduction than this, but to do so, you have to specify _better_ in which sense.  
> **username_0**: @jukka  I need a polynomial reduction to the problem s to Feedback vertex ,so that i can use approximation algorithm of feedback vertex set problem or to $k^2$ Kernelization of feedback vertex set in decision problem  
> **username_0**: @Tsuyoshi Example is correct but i want a polynomial reduction directly from s to feedback vertex set.  
> **username_5**: You can always construct a “direct” reduction by composing several reductions.  This is why I think you did not state the question correctly.  To state a question, you have to put some effort to clarify what you really want to know.  
> **username_0**: i want a reduction from problem S to feedback vertex set 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'  
> **username_5**: 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.  
> **username_3**: RE: My earlier comment, Tsuyoshi's response, and Emil's question: Let G be the complete graph on four vertices, let C be the "box" cycle that connects all four vertices. In this case, you cannot remove any of the triangle cycles unless you break C as well. What would the correct answer to S be in this case? 0? No correct answer? This makes me believe S needs to be re-worded a tad...  
> **username_5**: @Daniel: My interpretation of the problem S was that you can break any of the given cycles if you want to.  If this is what the questioner’s intent, the answer to your case is 2 because you have to remove the four triangles anyway.  But of course I do not know what the questioner’s intent really is.  
> **username_0**: @Daniel your question does not have answer as all vertices of all cycles are connected to C  
> **username_0**: @Tsuyoshi we are not allowed to break the cycles  
> **username_0**: @Tsuyoshi If u have reduction assuming that cycle $C$ can be allowed to break. please post your idea.  
> **username_5**: I do not have a reduction with the stated property under either interpretation.  

---

## 1 answers

### Answer by username_6 on 2010-10-05. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: sorry $\emptyset$ is misspelled as $\NULL$ and  i =3 $\ldots$ n not k. i could not edit back  
> **username_0**: 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 .  
> **username_0**: @karolina I do not get it why there should be a path from $v_{1}$ to $v_{4}$ through the forbidden cycle.  
> **username_0**: 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.  
> **username_0**: is it possible to have a similar kind of reduction when we are allowed to break these cycles.  

---

