17x17: PARTIAL-(n,m,c) is NP-complete

Update (2012.05.18): Bill Gasarch and I have written a paper on the subject. You may find it easier to follow. Also, the $12 \times 21$ problem has since been solved.

Intro

The 17x17 problem has been the subject of recent attention. The question, which was solved in the affirmative, asks whether it is possible to $4$-color the $17 \times 17$ grid such that no rectangle exists within the grid having all four corners the same color. The remaining unanswered question for $4$-colorings is whether there exists a coloring of the $12 \times 21$ grid also without monochromatic rectangles.

The $17 \times 17$ problem and the $12 \times 21$ problem are specific instances of the problem of $4$-coloring for grids. The general question for $n \times m$ grids with rectangle-free $c$-colorings is the $(n,m,c)$ problem. A related question is whether a partial coloring of a grid can be extended to a full coloring. The difficulties involved in completing $(n,m,c)$ grids suggest the problem is NP-complete. This is proved here.

Definition

The $n \times m$ grid is $c$-colorable if there is a way to color the vertices of the grid with $c$ colors so that no rectangle exists with all four corners the same color (Gasarch). The PARTIAL-$(n,m,c)$ decision problem asks whether a partial coloring of an $n \times m$ grid can be continued to a complete $c$-coloring.

PARTIAL-$(n,m,c)$ is NP-complete

Proof. By reduction from 3-SAT. Consider the following gadget.


F 210( z)                                 WB       
F 210(¬z)                              WB WB
F 210( z)                           WB WB
F 210(¬z)                        WB WB
F 210( z)                        WB                  B   
F   .  . 
F   .  .
F   .  .                                             
F 210( y)                      WB                     
F 210(¬y)                   WB WB
F 210( y)                WB WB
F 210(¬y)             WB WB                   
F 210( y)             WB                         ?   ?
F   .  .                                         W   W
F   .  .                       F
F   .  .
F 210( x)           WB 
F 210(¬x)        WB WB
F 210( x)     WB WB
F 210(¬x)  WB WB
F 210( x)  WB                                    B 
F   .  .
F   .  .
F   .  .
F 210  0...                                      0...0
F 210  1...                                      1...1
F 210  2...                                      2...2
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFF

Imagine that $( x)$ or $(\neg x)$ are of single-character width. Let $W$ indicate true and $B$ indicate false. All positions in the grid will begin colored except for the positions indicated by variables (e.g. $(x)$ or $(\neg x)$) and $?$'s (question marks).

New variables may be added by extending the construction vertically. The number of clauses in which a given variable $x$ appears will increase the number of rows of $x$ and $\neg x$ needed.

For simplicity's sake the 3-SAT clause $(x \vee y \vee z)$ is shown. The core of the gadget consists of the two question marks, the adjacent two $W$'s, and the two $B$'s in the columns corresponding to the $W$'s. The two question marks create a $W$ rectangle if and only if all $x,y,z$ are $B$. One entry in the clause must be true. By placing similar constructions strictly to the right of existing constructions you may add clauses arbitrarily.

For readability the pictured gadget leaves many positions unspecified. These positions need to be filled with inactive colors which cannot affect the core function of the gadget. The spots marked $F$ indicate one example filler color. Additional filler colors can be generated for each otherwise unfilled position in the grid. (Note the $F$ in the center of the construction.) To fill an unfilled position in the grid, add a column of $F~'$ to the far left, put $F~'$ in the desired spot, and add a row of $F~'$ to the bottom of the grid with a gap in the column of the newly filled position.

The free colors $0,1,2,\ldots$ show how arbitrary colors can be added without materially affecting the construction. Free colors can be used to fill the gaps in the bottom rows of filler colors.