It is $NP$-hard to decide if a $4$-regular planar graph can be $3$-colored.

Is an exact algorithm possible that under uniform distribution is in average polynomial time?

  • 2
    $\begingroup$ why the downvotes? $\endgroup$
    – Mark S
    May 29 '19 at 23:05
  • 1
    $\begingroup$ @Saeed I misread "It is NP-hard" for "is it NP-hard". Now I see that the only question here is about the average case (I thought there were two questions: NP-hardness, and average case.) $\endgroup$ May 31 '19 at 13:36
  • $\begingroup$ @SashoNikolov So average case is unlikely to be easy? $\endgroup$
    – Mr.
    May 31 '19 at 14:29
  • 4
    $\begingroup$ I don't know. But your question is missing important details. What is the distribution on inputs: uniform on 4-regular planar graphs of a fixed size? What notion of "easy on average" do you have in mind? Should the algorithm be polytime in expectation and always output the correct answer? Should the algorithm run in polytime in the worst case and output the correct answer with high probability under the distribution? Or maybe you mean Levin's definition? $\endgroup$ May 31 '19 at 20:06
  • $\begingroup$ @SashoNikolov clearer? $\endgroup$
    – Mr.
    Jun 1 '19 at 9:08

Your Answer

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

Browse other questions tagged or ask your own question.