CODEWITHSUNDEEP
algorithmproofcomputation-theorynp-completesatisfiability
Learner
Learner

Reputation: 1667

Can You Reduce K-Independent Set to 2-SAT

This is a homework question to start out. I just have some questions before I begin.

Our problem is:

"Reduce from k-Independent Set to 2−SAT as follows. Given a graph G with n vertices form n propositions, one per vertex. Each proposition xi for vertex i is set to true iff the vertex i belongs to an indepdenent set. Now for every edge (u,v) write a clause that says both u and v cannot belong to the independent set."

My question is that everything I read says 2-SAT is not an NP-Complete problem. How can we be reducing from the Independent Set problem then?

Upvotes: 1

Views: 2148

Answers (1)

CliffordVienna
CliffordVienna

Reputation: 8235

There is an important difference between finding any independent set and finding a maximum independent set (independent set of maximum size).

Finding any independent set nicely reduces to 2-SAT, using the reduction you described in your question. Neither problem is NP-complete. Note that the reduction you described in your question does not constrain the number of nodes in the independent set in any way. Even the empty set will satisfy the 2-SAT problem that is produced by this reduction, because the empty set also is an independent set!

Finding a maximum independent set (or k-independent set) however is an NP-complete problem. It does not reduce to 2-SAT.

Or in other words: The k in "k-Independent Set" is an additional constraint that is not part of this 2-SAT reduction (that's why the k is not even mentioned in the description of the reduction). You could add additional clauses to the SAT problem to count the number of included nodes and enforce that this number is at least k, but you can't do that by adding only 2-clauses. So adding the k is the step where your 2-SAT problem becomes an NP-complete general SAT problem.

MAX-2-SAT is an NP-complete extension of 2-SAT that can also be used to solve the maximum independent set problem using the reduction you posted. (You'd need two trivial modifications to the reduction: (1) Add 1-clauses for each proposition and (2) duplicate the 2-clauses for weighting.)

Upvotes: 2

Related Questions