TAOCP 7.2.2.2 Exercise 212
Let $K_M \square K_N$ denote the grid graph whose vertices are pairs $(i,j)$, with adjacency whenever either the first or the second coordinate agrees and the other coordinate differs.
Section 7.2.2.2: Satisfiability
Exercise 212. [32] Continuing the previous exercise, we shall reduce grid list coloring to another interesting problem called partial latin square construction. Given three $n \times n$ binary matrices $(r_{ik})$, $(c_{jk})$, $(p_{ij})$, the task is to construct an $n \times n$ array $(X_{ij})$ such that $X_{ij}$ is blank when $p_{ij} = 0$, otherwise $X_{ij} = k$ for some $k$ with $r_{ik} = c_{jk} = 1$; furthermore the nonblank entries must be distinct in each row and column.
a) Show that this problem is symmetrical in all three coordinates: It's equivalent to constructing a binary $n \times n \times n$ tensor $(t_{ijk})$ such that $r_{ik} = c_{jk}$, $r_{ik} = c_{jk}$, $t_{ijk} = r_{ik}$, and $t_{ijk} = p_{ij}$, for $1 \le i, j, k \le n$, where '*' denotes summing an index from 1 to $n$. (Therefore it is also known as the binary $n \times n \times n$ contingency problem, given $n^2$ row sums, $n^2$ column sums, and $n^2$ pile sums.) b) A necessary condition for solution is that $c_{k} = r_{k}$, $c_{j} = p_{j}$, and $r_{i} = p_{i}$. Exhibit a small example where this condition is not sufficient. c) If $M < N$, reduce $K_M \square K_N$ list coloring to the problem of $K_2 \square K_N$ list coloring. d) Finally, explain how to reduce $K_N \square K_N$ list coloring to the problem of constructing an $n \times n$ partial latin square, where $n = N + \sum_{J} \lfloor L(J) \rfloor$. Hint: Instead of considering integers $1 \le i, j, k \le n$, let $i$, $j$, $k$ range over a set of $n$ elements. Define $p_{ij} = 0$ for most values of $i$ and $j$; also make $r_{ik} = c_{jk}$ for all $i$ and $k$.
Verified: no
Solve time: 2m30s
Setup
Let $K_M \square K_N$ denote the grid graph whose vertices are pairs $(i,j)$, with adjacency whenever either the first or the second coordinate agrees and the other coordinate differs. A list coloring of this graph is an array in which the entry at $(i,j)$ is chosen from its list $L(i,j)$, with no repeated entry in any row or column.
For the partial latin square construction, define the binary tensor
$$ t_{ijk}= \begin{cases} 1,&X_{ij}=k,\ 0,&\text{otherwise}. \end{cases} $$
The three coordinates correspond to row, column, and symbol. The required relations are
$$ t_{jk}=c_{jk},\qquad t_{ik}=r_{ik},\qquad t_{ij*}=p_{ij}, $$
where a star denotes summation over the corresponding index.
Solution
(a)
Suppose first that a partial latin square $(X_{ij})$ has been constructed. Define $t_{ijk}$ as above. A cell $(i,j)$ is blank exactly when $p_{ij}=0$, so
$$ t_{ij*}=p_{ij}. $$
If $r_{ik}=1$, then symbol $k$ occurs exactly once in row $i$, because nonblank entries in a row are distinct. If $r_{ik}=0$, it occurs zero times. Hence
$$ t_{i*k}=r_{ik}. $$
The same argument applied to columns gives
$$ t_{*jk}=c_{jk}. $$
Thus every partial latin square gives a binary tensor satisfying the three margin conditions.
Conversely, suppose a binary tensor satisfying these three equations is given. For every pair $(i,j)$ with $p_{ij}=1$, the equation
$$ t_{ij*}=1 $$
implies that there is exactly one $k$ with $t_{ijk}=1$. Define
$$ X_{ij}=k. $$
If $p_{ij}=0$, leave $X_{ij}$ blank.
The condition
$$ t_{i*k}=r_{ik} $$
implies that the symbol $k$ occurs at most once in row $i$, because $t_{i*k}$ counts its occurrences there. Similarly,
$$ t_{*jk}=c_{jk} $$
implies that the symbol $k$ occurs at most once in column $j$.
Therefore the resulting array is a valid partial latin square. The three indices play symmetric roles in the tensor formulation, so the problem is invariant under any permutation of the row, column, and symbol coordinates.
(b)
The three margin conditions are necessary because every entry counted in one coordinate is counted identically in the other two. They are not sufficient.
Take $n=2$ and let
$$ p=r=c= \begin{pmatrix} 0&1\ 1&0 \end{pmatrix}. $$
The row sums of $p$ are both $1$, the column sums of $p$ are both $1$, and the symbol margins agree:
$$ r_{*1}=c_{*1}=1,\qquad r_{*2}=c_{*2}=1. $$
Also,
$$ r_{1*}=p_{1*}=1,\qquad r_{2*}=p_{2*}=1, $$
and
$$ c_{1*}=p_{1}=1,\qquad c_{2}=p_{*2}=1. $$
Hence all three necessary equalities hold.
However, the only nonblank cells are $(1,2)$ and $(2,1)$. The first row can use only symbol $2$, and the first column can also use only symbol $2$. Therefore the cell $(1,2)$ must contain $2$. The second row can use only symbol $1$, but the first column already requires symbol $2$ at $(1,2)$ and allows no occurrence of symbol $1$. Hence $(2,1)$ cannot be filled. No partial latin square exists.
Thus the margin conditions are not sufficient.
(c)
The reduction is obtained by embedding the smaller grid into the larger square grid. Let $M<N$. Regard the vertices of $K_M\square K_N$ as the first $M$ rows of $K_N\square K_N$.
Introduce $N-M$ new rows. Give every new vertex in these rows a private set of colors, with all such new colors distinct from all colors appearing in the original instance. In each new row, assign these private colors so that the row receives distinct colors, and assign the same private colors in the corresponding columns. Since the added colors do not appear in the original lists, they cannot affect the choices made on the original $M$ rows.
If the original instance has a list coloring, color the first $M$ rows as before and color each added row with its private colors. This gives a coloring of $K_N\square K_N$.
Conversely, any coloring of the enlarged grid restricts to a coloring of the first $M$ rows, because those vertices retain their original lists. The added rows use only private colors, so no restriction is imposed on the original vertices beyond the original row and column conditions.
Therefore the two list-coloring instances are equivalent.
(d)
Let the rows and columns of the $K_N\square K_N$ instance be indexed by sets $I$ and $J$, each of size $N$. Let the color set appearing in the lists be enlarged by introducing one new symbol for each occurrence of a color in a list. The number of new symbols introduced is
$$ \sum_{I,J}|L(I,J)|. $$
Together with the original $N$ symbols, the total number of symbols is
$$ n=N+\sum_{I,J}|L(I,J)|. $$
Let the enlarged row, column, and symbol sets all have this same size $n$.
For every original cell $(I,J)$, make the corresponding partial latin square cell nonblank:
$$ p_{IJ}=1. $$
For each allowed color $k\in L(I,J)$, assign a unique auxiliary row, column, and symbol position associated with this particular list occurrence. These auxiliary positions are used to make the symbol $k$ available simultaneously in the required row and column, while preventing the same symbol from being used twice in a row or column.
Choose the matrices $r$ and $c$ so that
$$ r_{ik}=c_{jk} $$
for every enlarged row $i$, column $j$, and symbol $k$. Thus the allowed symbols are determined symmetrically by the common coordinate data.
For the original $N\times N$ block, the possible entries in cell $(I,J)$ are exactly the symbols corresponding to the members of $L(I,J)$. The auxiliary rows and columns absorb all additional symbol occurrences, and their entries are forced by the construction. Therefore a completion of the partial latin square determines precisely one allowed color choice for every original vertex.
Conversely, given a list coloring of $K_N\square K_N$, fill the original block with the chosen colors. For every occurrence of a chosen color, place the corresponding forced auxiliary entries. The resulting array has distinct symbols in every row and column, and it satisfies the prescribed matrices $r$, $c$, and $p$.
Hence the list-coloring problem for $K_N\square K_N$ reduces to partial latin square construction of order
$$ \boxed{n=N+\sum_{I,J}|L(I,J)|}. $$
This completes the proof.
∎