4
$\begingroup$

We have an $n\times n$ grid of squares, each square has a non-negative integer. Two distinct squares are neighbours if they share a row or column. A selection of squares is good if every selected square has a number of selected neighbours less than or equal to its number.

Is there a known way to find the maximum number of elements in a good selection? Clearly there is a $\mathcal O(2^{n^2}n^2)$ brute force algorithm (we can test for goodness of a selection in time $\mathcal O (n^2)$ by precomputing number of selected squares in each row and column).

$\endgroup$
  • $\begingroup$ one optimization would be to generate the selections lexicographically and "skip" impossible selections as soon as a mistake is found. But this is not good when the numebrs on the grid are large. $\endgroup$ – Jorge Fernández Aug 22 '17 at 23:37
  • 2
    $\begingroup$ (Assuming Yuval's guess.) If all squares have $0$, this is Independent Set, which is NP-complete. Hence, this problem is at least as hard (special case reduction). I'm sure there's a better algorithm than brute-force, though. $\endgroup$ – Raphael Aug 23 '17 at 7:49
  • 3
    $\begingroup$ @Raphael The problem is easy if all squares have 0, since it's a particular graph. The best you can do is pick a "generalized diagonal" consisting of $n$ vertices, one on each row and column. $\endgroup$ – Yuval Filmus Aug 23 '17 at 7:58
  • $\begingroup$ @YuvalFilmus Quite right, my bad. $\endgroup$ – Raphael Aug 23 '17 at 9:21
  • $\begingroup$ @D.W that sounds interesting, could you give a sketch of the dp? $\endgroup$ – Jorge Fernández Aug 24 '17 at 19:36
1
$\begingroup$

There is a dynamic programming algorithm whose running time is $O(2^{4n})$.

Suppose we have already chosen a configuration for the first $i$ columns. Mark a cell in the $i$th column as "red" if the cell to its right cannot be selected (i.e., the number of selected neighbors, not counting its right neighbor, is equal to the number in that cell), or "green" if the cell to its right can be selected.

Let $c \in \{R,G\}^n$ be a sequence of $n$ colors, and $x \in \{0,1\}^n$ be a sequence of $n$ bits. Define $A[i,c,x]$ to be the maximum number of elements in a good selection for the first $i$ columns that induces the coloring $x$ on the $i$th column and where $x$ describes which cells are selected in the $i$th column. Then it is easy to calculate $A[i+1,c',x']$ from $A[i,c,x]$: we have

$$A[i+1,c',x'] = |x'| + \max_{c,x} A[i,c,x],$$

where the max is taken over all $c,x$ that are consistent with $c',x'$ (i.e., such that it's possible to have a selection for the first $i+1$ columns that has selection $x$ in column $i$, selection $x'$ in column $i+1$, colors $c$ in column $i$, and colors $c'$ in column $i+1$). To be consistent, we must have $c_j=R \implies x'_j=0$ for all $j$, and $x_j + x'_{j-1} + x'_{j+1}$ must be at most the number in column $i+1$, row $j$ (and $c'_j=R$ iff they are equal).

This yields a dynamic programming algorithm with $O(n \times 2^{4n})$ running time: we need to fill in $n \times 2^{2n}$ entries of $A[\cdot,\cdot,\cdot]$, and each entry requires us to compute a max over at most $2^{2n}$ numbers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.