Question

On page $\mathbf{266}$we saw that 3SATremainsNP-complete even when restricted to formulas in which each literal appears at most twice.

(a)Show that if each literal appears at mostonce,then the problem is solvable in polynomial time.

(b)Show that INDEPENDENT SET remains NP-complete even in the special case when all the nodes in the graph have degree at most $\mathbf{4}$.

Short answer

(a)This problem is solved in a polynomial time. Hence, the given statement has been proved.

(b)The given statement has been proved.

Step-by-step solution

Define 3-SAT

3-SAT is an abbreviation for 3-satisfiability, which is the Boolean satisfiability problem where each clause contains $\mathbf{3}$ literals or variables.

Prove the given problem is solvable in polynomial time

(a)

Consider the information: 3-SAT is an abbreviation for 3-satisfiability, which is the Boolean satisfiability problem where each clause contains 3 literals or variables.

Proof:

If in the 3SAT problem each literal seems at most once, then this is classified into these following cases for literals $l$ and$\neg$ :

If $l$ seems in clause$d$ , then set the value of the literal $\mathrm{l}=\mathrm{true}$ and ignore $\mathrm{d}$.

If $\neg$ only seems in clause d, then set the value of the literal role="math" localid="1658140114740" $\mathrm{l}=\mathrm{false}$ and ignore $d$.

If $\neg$ and $l$ both seem in clause $d$ only, then $l$ is either true or false or ignore $d$.

If $\neg$ and $l$ both seem in two different clauses, then take out the literal $l$ and then combine the left. After that set the value of literal $l$ when required.

If $l$ and $\neg$ are the only literals that seem in two clauses, that means it is not satisfiable. Thus, by applying this, eliminate each literal in linear time.

Therefore, this problem is solved in a polynomial time. Hence, the given statement has been proved.

Prove that INDEPENDENT SET remains NP Complete

(b)

Consider the information: In an independent set, there are no edges that are adjacent to each other. There is no common vertex also between the two edges. There are no vertices that are adjacent to each other. There is no common edge also between the two vertices. Proof: In the process of reducing the 3SAT problem into an independent set, if each variable seems at most twice, then any vertices’ degree cannot be greater than $4$. It means the 3SAT problem remains NP-Complete in the condition where each literal appears at most $2$ times. Therefore, the Independent Set also remains NP-Complete in the condition when each node has the degree at most $4$.

Hence, the given statement has been proved.