(Paraphrase) Find a 4-coloring of the 17x17 grid that has
no monochromatic rectangles. For $289.00. It was solved in 2012
by Bernd Steinbach and Christian Posthoff (I posted about it
and will post their paper when they make it it is public, which should be soon.)
Even though it was solved, it seemed to be a hard problem.
On April 28, 2010 (before the problem was solved)
I wondered WHY it was so hard and posted the following question:
(Paraphrase) Consider the following problem:
Given (N,M,c,f) where f is a partial c-coloring of NxM,
can f be extended to a total c-coloring of NxM (without mono rectangles)?
Is this problem NP-complete?
Kevin Lawler emailed
me a sketch of a proof recently! So YES, it is NP-complete!
I cleaned it up, wrote it up, and put in a few other things, and the paper is
(We will be posting to arXiv after we get comments from this blog.)
- Does this really show why the 17x17 challenge was hard?
Not really since the 17x17 challenge is just one instance.
- Does this show that grid coloring problems are hard in general?
Not really since the case we are really interesting in is where
f is the empty function. While we do not believe this case is
easy, we have not ruled this out.
- What can we show about the algorithmic complexity?
The problem is FPT. For fixed c its in time poly(N,M)+O(cc4).
While this work is very interesting
it is NOT the same as showing that finding Ramsey Numbers is hard.I suspect that to prove such things we need a new framework for