<p>It is <span class="math-container">$NP$</span>-hard to decide if a <span class="math-container">$4$</span>-regular planar graph can be <span class="math-container">$3$</span>-colored. </p>

<p>Is an exact algorithm possible that under uniform distribution is in average polynomial time?</p>

CC BY-SA 4.0
2019-05-29T23:05:35.110Z
why the downvotes?
Mark S
CC BY-SA 4.0
2019-05-31T13:36:04.397Z
@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.)
Sasho Nikolov
CC BY-SA 4.0
2019-05-31T14:29:41.627Z
@SashoNikolov So average case is unlikely to be easy?
Turbo
CC BY-SA 4.0
2019-05-31T20:06:35.620Z
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](http://www.wisdom.weizmann.ac.il/~/oded/COL/lnd.pdf)?
Sasho Nikolov
CC BY-SA 4.0
2019-06-01T09:08:01.670Z
@SashoNikolov clearer?
Turbo
CC BY-SA 4.0
2019-06-01T16:16:19.663Z
Yes. BTW, if the answer is "no, there is no polytime on average algorithm", then I doubt whether we have the tools to show something like this. Also this special case is quite obscure IMO, so I also doubt anyone has actually thought about it.
Sasho Nikolov
<graph-colouring><average-case-complexity>
On planar $4$ regular graphs
Turbo
# On planar $4$ regular graphs

(Asked by: username_0 on 2019-05-29)

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?

**Tags:** graph-colouring, average-case-complexity
> **Comments:**
> **username_1**: why the downvotes?  
> **username_2**: @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.)  
> **username_0**: @SashoNikolov So average case is unlikely to be easy?  
> **username_2**: 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](http://www.wisdom.weizmann.ac.il/~/oded/COL/lnd.pdf)?  
> **username_0**: @SashoNikolov clearer?  
> **username_2**: Yes. BTW, if the answer is "no, there is no polytime on average algorithm", then I doubt whether we have the tools to show something like this. Also this special case is quite obscure IMO, so I also doubt anyone has actually thought about it.  

---

## 0 answers

