# NP-completeness of graph isomorphism through edge contractions with an edge validity condition

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 ?

• possible duplicate of $NP$-completeness proof – JeffE Jul 6 '12 at 14:05
• Simultaneously cross-posted at cstheory. Please don't do that. Again. – JeffE Jul 6 '12 at 14:06
• Okay I will not. – user1403806 Jul 6 '12 at 22:56

• 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