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, 2019 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, 2019 at 13:36
  • $\begingroup$ @SashoNikolov So average case is unlikely to be easy? $\endgroup$
    – Turbo
    May 31, 2019 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, 2019 at 20:06
  • $\begingroup$ @SashoNikolov clearer? $\endgroup$
    – Turbo
    Jun 1, 2019 at 9:08


Your Answer

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