8
$\begingroup$

I am considering the following problem:

Input: 3 graphs $G=(V,E)$, $H_1$, $H_2$
Question: Is there some $V_1\subseteq V$ such that $G[V_1]$ (the subgraph induced by $V_1$) is isomorphic to $H_1$, and $G[V\backslash V_1]$ is isomorphic to $H_2$?

It is clearly at least as hard as Graph Isomorphism (take the empty graph for $H_2$), and in NP (certificate: $V_1$ and the isomorphisms). Intuitively, it should be easier than subgraph isomorphism, since here we know what the "complement" looks like.

I have several questions regarding this:

  • Has it been studied / does it have a name?
  • If yes, is it NP-hard?
  • If still yes, has it been studied on restricted graph classes?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

Your problem is NP-complete. Two-colorable perfect matching (which is NP-complete even when restricted to cubic planar graphs) is reducible to your problem. Take $H_1$ and $H_2$ to be perfect matchings each of $|V|/2$ nodes. Then your problem is to find 2-coloring of $V$ such that each color class induces a perfect matching.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Splendid! If anyone's interested, it appears that this result is from Schaeffer '78 The Complexity of Satisfiability Problems $\endgroup$
    – tarulen
    Commented Apr 27, 2016 at 13:50

Your Answer

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

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