1
$\begingroup$

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'

Improve this question
$\endgroup$
17
  • 3
    $\begingroup$ please note the edits to the text. In the future, it would be helpful to format your questions in this manner. $\endgroup$
    – Suresh Venkat
    Sep 13, 2010 at 8:21
  • 1
    $\begingroup$ 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.? $\endgroup$
    – Jukka Suomela
    Sep 13, 2010 at 8:53
  • 1
    $\begingroup$ Must the cycles $C_1, \dots, C_n$ be left intact? Are we allowed to break these cycles? $\endgroup$
    – Emil
    Sep 13, 2010 at 10:19
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Sep 13, 2010 at 12:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Sep 14, 2010 at 11:21

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Prabu
    Oct 6, 2010 at 7:00
  • $\begingroup$ sorry $\emptyset$ is misspelled as $\NULL$ and i =3 $\ldots$ n not k. i could not edit back $\endgroup$
    – Prabu
    Oct 6, 2010 at 7:09
  • $\begingroup$ 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 . $\endgroup$
    – Prabu
    Oct 7, 2010 at 5:43
  • $\begingroup$ @karolina I do not get it why there should be a path from $v_{1}$ to $v_{4}$ through the forbidden cycle. $\endgroup$
    – Prabu
    Oct 7, 2010 at 5:48
  • $\begingroup$ 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. $\endgroup$
    – Prabu
    Oct 7, 2010 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.