h3. Soluţie

Dacă între două noduri există muchie atunci nu pot fi amândouă în mulţimea <tex> I </tex>, iar dacă între două noduri nu există muchie nu pot fi amândouă în mulţimea <tex> C </tex>.
Transformăm această problemă într-o instanţă de $2SAT$ astfel: faptul că nodul <tex> x </tex> aparţine mulţimii <tex> C </tex> îl reprezentăm dândui lui <tex> x </tex> valoarea <tex> 1 </tex>, iar apartenenţa mulţimii <tex> I </tex> se codifică prin valoarea <tex> 0 </tex>. Acum existenţa unei muchii <tex> (x, y) </tex> corespunde expresiei <tex> x \vee y </tex>, astfel cel puţin unul din nodurile <tex> x </tex> şi <tex> y </tex> nu va fi în mulţimea <tex> I </tex>. Dacă nu există muchia <tex> (x, y) </tex> putem scrie <tex> \sim x \vee \sim y </tex>, această expresie va fi adevărată dacă cel puţin un nod din cele două nu va fi în mulţimea <tex> C </tex>.

Dacă între două noduri există muchie atunci nu pot fi amândouă în mulţimea $I$, iar dacă între două noduri nu există muchie nu pot fi amândouă în mulţimea $C$.
Transformăm această problemă într-o instanţă de $2SAT$ astfel: faptul că nodul <tex> x </tex> aparţine mulţimii $C$ îl reprezentăm dândui lui <tex> x </tex> valoarea <tex> 1 </tex>, iar apartenenţa mulţimii $I$ se codifică prin valoarea <tex> 0 </tex>. Acum existenţa unei muchii <tex> (x, y) </tex> corespunde expresiei <tex> x \vee y </tex>, astfel cel puţin unul din nodurile <tex> x </tex> şi <tex> y </tex> nu va fi în mulţimea $I$. Dacă nu există muchia <tex> (x, y) </tex> putem scrie <tex> \sim x \vee \sim y </tex>, această expresie va fi adevărată dacă cel puţin un nod din cele două nu va fi în mulţimea $C$.

Această soluţie este liniară ca şi complexitate în numărul de elemente citite la intrare.