An NP Problem Named All But Five Three Colorable(AB53C) is defined as follows :- Input : Connected Graph G(V,E) The Connected Graph is AB53C, iff the Given Graph is 3-Colorable by leaving UPTO 5 Vertices Uncolored.

Question:- The Problem is in NP. Show the reduction from 3-Colorable Problem.

The Proposed Solution is :-

Find Permutation of All Subsets where |V'| = |V| - 5. Basically these subsets will have 5 vertices less than the original set. Remove all edges from V' to V. All such subsets are found out and then passed through the 3-Color. If we get YES on any one of these Subgraphs, then we have a AB53C.

I want someone disprove my method OR show that the reduction is non-polynomial. Otherwise, my proposal is correct.

  • $\begingroup$ @YuvalFilmus: Can you suggest a reduction? I have a proposal, but I dont want to contaminate the readers thought by my proposal. $\endgroup$ – ARK Dec 5 '14 at 3:19
  • $\begingroup$ I suggested a reduction in my answer. But generally on this site we appreciate people showing effort on solving their questions on their own. For example, if you have a proposed reduction but can't prove that it works, you could share it with us. $\endgroup$ – Yuval Filmus Dec 5 '14 at 3:25
  • 1
    $\begingroup$ (Polynomial time) many-one reductions are the ones appearing in the definition of NP-hardness. If you look at any textbook or lecture notes (or even Wikipedia) on NP-hardness, I'm sure you'll find a definition and examples. $\endgroup$ – Yuval Filmus Dec 5 '14 at 4:21
  • 1
    $\begingroup$ Why do you doubt your approach? Do you have a specific question, i.e. one distinct from "please grade my hand-in"? $\endgroup$ – Raphael Dec 5 '14 at 11:38
  • 1
    $\begingroup$ @user10584 That's fine, but simply not what SE is suitable for. $\endgroup$ – Raphael Dec 5 '14 at 18:25

Hint: Add a clique on 8 vertices to the graph.

  • $\begingroup$ Clique is a Complete Graph. It will consider cases for Complete Subgraphs only. WE have a connected Graph. $\endgroup$ – ARK Dec 5 '14 at 3:48
  • $\begingroup$ Right, you'll have to connect the clique to the rest of the graph in a smart way. You'll also have to connect the various connected components of the original graph in a smart way. $\endgroup$ – Yuval Filmus Dec 5 '14 at 3:50

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.