Given Graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$. Can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions ? We know this problem is NP-complete. What about if only a subset of edges are valid for contraction at each step of the sequence. For example when deciding the first edge for contraction, there are only a subset $E'\subset E_1$ of edges eligible for contraction. If you pick $e\in E'$ for contraction and get an intermediate graph then when deciding the second edge for contraction in this intermediate graph there are a subset $E''$ of edges eligible for contraction and so on.

Does this problem stay NP-complete ?

The answer is yes. Suppose that you had a polynomial-time algorithm to solve your revised problem. Apply that algorithm to the special case where the subset of edges available at each step is the whole set. We'd then have a polynomial time algorithm for the original, known NP-complete, problem.

To have any hope of dreaming up a non-NP-complete version, you'd need to put a restriction on the subsets that were eligible that would prevent an immediate reduction to the original problem. At that point you'd have a new problem which you cannot easily show is NP-complete. However it is in the nature of NP-complete problems that, if your restriction avoids 2+ choices at each step, it very likely to be NP-complete.

(Note, it is currently unknown whether the simpler problem of identifying whether two graphs are isomorphic is NP-complete.)

  • Thanks Btilly. What do you mean by "if your restriction avoids 2+ choices at each step" ? What is "2+" ? – user1403806 Jul 6 '12 at 11:28
  • But if the subsets are $O(\log n)$ then it's clearly in P... the question needs more definition – Xodarap Jul 6 '12 at 15:44
  • What if at each step the subset of edges is a strict subset and definitely not a whole set ? This means the original graph contraction problem is not a special case of our problem. – user1403806 Jul 6 '12 at 20:09
  • @Xodarap Not clearly in P. As I noted, the much problem of whether two graphics are isomorphic is itself not known to be in P. – btilly Jul 7 '12 at 1:10
  • @user1403806 If you can write down a problem searching through a decision tree where each of n decisions has 2 or more choices, there is a tendency for your problem to wind up NP-complete. As for your subset problem, take the first graph, put a vertex in the middle of each edge. On your odd steps you can only remove the top half of an edge, on your even steps you remove the bottom half. Now you only have a proper subset of edges each time but still can solve the original NP-complete problem. So no, "proper subset" does not help you. – btilly Jul 7 '12 at 1:12

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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