5
$\begingroup$

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 ?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ possible duplicate of $NP$-completeness proof $\endgroup$
    – JeffE
    Jul 6, 2012 at 14:05
  • 3
    $\begingroup$ Simultaneously cross-posted at cstheory. Please don't do that. Again. $\endgroup$
    – JeffE
    Jul 6, 2012 at 14:06
  • $\begingroup$ Okay I will not. $\endgroup$
    – user1403806
    Jul 6, 2012 at 22:56

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thanks Btilly. What do you mean by "if your restriction avoids 2+ choices at each step" ? What is "2+" ? $\endgroup$
    – user1403806
    Jul 6, 2012 at 11:28
  • $\begingroup$ But if the subsets are $O(\log n)$ then it's clearly in P... the question needs more definition $\endgroup$
    – Xodarap
    Jul 6, 2012 at 15:44
  • $\begingroup$ 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. $\endgroup$
    – user1403806
    Jul 6, 2012 at 20:09
  • $\begingroup$ @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. $\endgroup$
    – btilly
    Jul 7, 2012 at 1:10
  • $\begingroup$ @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. $\endgroup$
    – btilly
    Jul 7, 2012 at 1:12

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.