I am having trouble solving the following question.

I am given a following problem X: Given a graph G, we want to know whether there is an edge e in G such that G − e is 3-colorable.

I want to show that $X \leq_p 3Col$

My attempt is to look at the complement of G, and say that the complement of G shows us that the graph plus the edge is not 3-colorable if and only if the G - e is 3-colorable.

Does this make sense and is it correct?

  • 1
    $\begingroup$ Try to prove that your reduction works, and see for yourself. $\endgroup$ – Yuval Filmus Mar 15 '16 at 21:09
  • $\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. Mar 16 '16 at 0:54

Since 3COL is NP-hard and X is clearly in NP, by definition there is some many-one reduction from X to 3COL, though it may be awkward to state. There is a simple oracle reduction along the lines outlined in the other answer: remove each edge at a time, and check if the resulting graph is 3-colorable.

More interesting, perhaps, is a reduction going the other way, thus showing that X is NP-hard (and so NP-complete). Given a graph, we adjoin to it $K_4$, the clique on 4 vertices. The new graph is a Yes instance of X iff the original graph is 3-colorable (exercise).

| cite | improve this answer | |
  • $\begingroup$ I've been thinking about the exercise you proposed, and was wondering why we adjoin the graph to a clique of 4 vertices $\endgroup$ – user270494 Mar 16 '16 at 3:47
  • $\begingroup$ @user270494 You'll see the answer when you solve the exercise. $\endgroup$ – Yuval Filmus Mar 16 '16 at 7:01

Try removing each edge and checking if the remainder of the graph is 3-colorable. In this way you have shown that $X \leq E. 3Col$ in which $E$ is the number of edges and therefore polynomial.

| cite | improve this answer | |
  • $\begingroup$ Please don't use answers to comment on the question or request clarification about the question. This is a question-and-answer site, not a discussion forum: please reserve the answer box only for material that answers the question that was asked. Thank you! $\endgroup$ – D.W. Mar 21 '16 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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