This is from the Algorithms textbook by Dasgupta,C. H.Papadimitriou,andU. V. Vazirani question 8.6 (b) that asks:
And missing from the pic as @Nathaniel points out in his answer below: "3SAT remains NP-complete even when restricted to formulas in which each litteral appears at most twice".
My reduction from Clique:
Definition of clique: fully connected graph/subgraph
So given G=(V,E) and a goal g it returns a clique of size g fully connected.
The complement graph G’ would contain an IS of size g of the same vertices.
So given a graph G, with degree at most 4, as input to Clique, the largest possible clique would be of size 5 vertices per the definition. Let's assume g=5 as input to the Clique problem.
Make the complement graph G’ =(V, E’) where uv in E’ not in E and call ISdeg4 on G’ with g=5.
If there is an IS of size g=5 in G’, then those 5 vertices make up a clique in G so return that to Clique.
Else returns no which I can return to Clique.
ISdeg4 is in NP:
Returns a set of vertices which are an IS.
In O(n+m) I can check that none of the v's in the IS have an edge to another v in the IS.
So ISdeg4 can be used to solve Clique problems for G=(V,E) with degree at most 4.
The above is not a solution since the reduction from Clique to ISDeg4 only solves a subset of Clique problems where an input G=(V,E) is at most degree 4.
Thus, I want to know if anyone has a reduction from a known NP-Complete graph problem rather than 3SAT-> IsDeg4 which I was able to understand after seeing the solution given by my teacher.