How can I show that the following language is NP-Complete?

{(G, H) : G is a graph and H is a set of induced subgraphs of G such that it is possible to split the vertices of G into two sets A and B so that every subgraph in H contains at least one vertex from A and at least one vertex from B}

I have already proved that the language is in NP, so now it remains to show there is some polynomial time reduction from an NP-Complete language to this one.

Ideally, the solution would use either SAT or 3SAT as the starting point, since these are the languages I've seen being used for previous reductions.

I'm stuck at this point.

Thanks for your help.


I would suggest reducing instead from Not-All-Equal 3SAT, which requires at least one variable in each clause to be true, and at least one to be false.

From there things are fairly straightforward. To provide a further hint (for the sake of answer completeness), one should have a subgraph (in H) for each variable and each clause of the NAE-3SAT formula. The sets A and B will then correspond to the variable assignments.

As a side note, the phrasing of this problem is a little bit suspect, as the edges of the graphs are not used in the problem statement. (In particular, whether or not $(G,H)\in L$ is independent of the edges in $G$.) Unless I'm missing something, $G$ might as well be a set (with subsets in $H$) instead of a graph.

  • $\begingroup$ Thanks for your answer. It makes sense to me that each clause represents a subgraph, and so each clause will evaluate to 1 iff the subgraph contains at least one vertex in A (true) and one vertex in B (false). However, does this not restrict the problem to only subgraphs of size 3, since each clause has 3 variables? $\endgroup$ – user417638 Apr 12 '17 at 14:56
  • $\begingroup$ Yes, it seems the problem remains NP-hard even if all subgraphs in H have size at most 3. $\endgroup$ – SamM Apr 13 '17 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy