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.