0
$\begingroup$

This is from the Algorithms textbook by Dasgupta,C. H.Papadimitriou,andU. V. Vazirani question 8.6 (b) that asks:

questions pic Edit:

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.

Edit: 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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Please see Should we do anything about questions that are just a scan of a problem in their textbook? => "Posting text inside an image is not good because it is not searchable, whereas Stack Exchange posts are meant to be useful to future visitors, and that usefulness starts with said future visitors being able to find the post. Also, people who are blind or have very bad eyesight cannot read images." $\endgroup$
    – ggorlen
    Commented Apr 11, 2021 at 3:22
  • $\begingroup$ What is your question? I don't see a question here. We are a question-and-answer site, so we require you to articulate a specific question -- don't make us guess. $\endgroup$
    – D.W. ♦
    Commented Apr 11, 2021 at 7:26
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Commented Apr 11, 2021 at 7:26
  • $\begingroup$ @D.W. Please refer to the bottom edit. $\endgroup$
    – mLstudent33
    Commented Apr 11, 2021 at 17:25

1 Answer 1

Reset to default
1
$\begingroup$

As you stated, this is not a correct reduction, because you would need to solve Clique for any graph (or prove that Clique with graphs of degree at most 4 is $NP$-complete).

Actually, the question 8.6.b stands true if the graph have degree at most 3. I think the intention of the author for solving this exercice is to use the remark stated at the beginning of the exercice (which you cropped): "$\textsf{3SAT}$ remains $\textsf{NP}$-complete even when restricted to formulas in which each litteral appears at most twice".

You should then make a reduction from $\textsf{3SAT-2LITmax}$ (a convenient name I came up for the problem I just described), using the same kind of reduction to prove $\textsf{NP}$-hardness of $\textsf{IS}$ from $\textsf{3SAT}$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Actually the official solution shows 2LIT max -> ISdegMost4 and 2LITMax is already shown in section 8.3 of the book. $\endgroup$
    – mLstudent33
    Commented Apr 10, 2021 at 17:22
  • $\begingroup$ I had to edit my question as @D.W. pointed out. You are correct but I was looking for a reduction from a known NP-Complete Graph problem. $\endgroup$
    – mLstudent33
    Commented Apr 11, 2021 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.