3
$\begingroup$

I'm searching for the correct name of the following NP-complete problem. I would also appreciate answers pointing to problems with similar-looking variations.

The input consists of

  • A set of colors $\Sigma$ with $|\Sigma|=n^{O(1)}$.
  • An $nxn$ square matrix $M$ where each entry $M_{ij}$ is a subset of $\Sigma$
  • For each $i\in [n]$ and each $j\in [n-1]$, a set $H_{ij}\subseteq \Sigma\times \Sigma$ of horizontal constraints.
  • For each $i\in [n-1]$ and each $j\in [n]$, a set $V_{ij}\subseteq \Sigma\times \Sigma$ of vertical constraints.

A solution for the problem is an $n\times n$ matrix $N$ where each entry $N_{ij}$ belongs to $M_{ij}$, each pair horizontally consecutive entries $(N_{ij},N_{i(j+1)})$ belongs to $H_{ij}$ and each pair of vertically consecutive entries $(N_{ij},N_{(i+1)j})$ belongs to $V_{ij}$.

$\endgroup$
3
$\begingroup$

A1) The problem remains NP-complete even for fixed $|\Sigma|=3$

A reduction from planar 1-3-SAT is the following; suppose $\Sigma = \{0,1,2\}$

  • use a sequence of $M_{ij} = \{0,1\}$ pairs of horizontal/vertical cells as "wire" gadgets to "carry" the truth values ($0=true$, $1,2 = false$) of the variables (the horizontal and vertical rules of the wires forbid switching between $true \leftrightarrow false$)
  • the beginning of a wire acts as "variable assignment"
  • the clauses are simulated using a circular pattern in which the horizontal and vertical rules force a sequence of $012\;012....$ along the circuit
  • each clause has 3 incoming wires; the wires are arranged to "touch" the circuit in three distinct places modulo 3; in this way only one of the three wires can have the value of true.

The following figure should be self-explanatory.

enter image description here

If instead of "local" horizontal/vertical rules you want to use "global" rules (a set of rules that are common to all cells) then you must add another extra "blank" color to "isolate" the wires and the reduction above still holds.

With $|\Sigma| = 2$ the problem is polynomial time solvable (each cell is represented with a binary variable, and the rules can be expressed with a 2-SAT formula).

A2) The game is also very similar to a "relaxed" version of the game Binary Puzzle: a puzzle game played on a $n \times n$ grid. Intially some of the cells contain a zero or a one; the aim of the game is to fill the empty cells according to the following rules:

  1. Each cell should contain a zero or a one and no more than two similar numbers next to or below each other are allowed
  2. Each row and each column should contain an equal number of zeros and ones
  3. Each row is unique and each column is unique

Using a set of eight colors you can "simulate" the rule #1 of binary puzzle (which is NPC even without rules #2 and #3 ). This is a quick idea for a reduction.

Each one of the eight colors has 3 bits $b_0b_1b_2$;

  • bit 0 $b_0$ represents the $0$ or $1$ of the binary puzzle grid
  • bit 1 $b_1$ is $1$ if and only if the cell on the left has the same color
  • bit 2 $b_2$ is $1$ if and only if the cell above has the same color

If a cell $i,j$ of the initial board of binary puzzle is empty then you set $M_{ij} = \Sigma$

If a cell $i,j$ of the initial board of binary puzzle is a forced $1$ then you set $M_{ij} = \{ 1** \}$ (100,101,110,111)

If a cell $i,j$ of the initial board of binary puzzle is a forced $0$ then you set $M_{ij} = \{ 0** \}$ (000,001,010,011)

The horizontal rules are:

00* -> 01*  : allow another 0 on the right only if the previous was 1
0** -> 1**  : always allow a 0->1 transition
10* -> 11*  : allow another 1 on the right only if the previous was 0
1** -> 0**  : always allow a 1->0 transition

The vertical rules are:

0*0 -> 0*1  : allow another 0 below only if the above one was 1
0** -> 1**  : always allow a 0->1 transition
1*0 -> 1*1  : allow another 1 below only if the above one was 0
1** -> 0**  : always allow a 1->0 transition

You can find the proof of NP-completeness of binary puzzle on my blog (soon or later I'll find the time to submit it somewhere).

A3) Furthermore if you add the constraint that each color can be used only once, then the problem is still NPC even on $n \times 1$ grids with only horizontal constraints.

The reduction is from 3-PARTITION which is strongly NPC: given a set $X = \{x_1, ..., x_{3q}\}$ and a target sum $B = (\sum x_i)/3$; use (new) colors $c^i_1,...,c^i_i$ for each $x_i$. Start with a grid $G$ of length $Bq+q + 1$ with the following sets of allowed colors:

$S E^B T_1 E^B T...E^B T_q$

Where

  • $S$ (the set $M_1$) represents the starting color $\{ c_S \}$
  • $T_i$ represents a breaking block that contain $q$ special colors $\{ c_{Ti} \}$
  • $E^B$ is a sequence of $B$ "blocks" that can contain any color from $\Sigma \setminus \{ c_S, c_{Ti}\}$

The horizontal constraints are:

  • $(S,c^i_1)$ for $i = 1...n$: that allows to start from $S$ and start using a color sequence from $c^i$
  • $(c^i_j, c^i_{j+1})$ for $j = 1...i-1$: that forces the complete color sequence of each $c^i$ (once started)
  • $(c^i_i, c^j_1)$ for $i \neq j$ that allows to start another color sequence once ended the previous one
  • $(c^i_i, c_{Tj})$ for $i = 1...n, j=1..q-1$: that "align" the color sequences to the break blocks (that guarantee that the "unary" sum is equal to $B$)
  • $(c_{Tj}, c^i_1, )$ for $i = 1...n, j=1..q-1$: that allows another color sequence after a breaking block $T_j$

The $n \times 1$ grid $G$ can be properly colored if and only if the original 3-PARTITION problem has a solution.

This is an example: given the 3-PARTITION instance:

$A = \{ 3,3,2,2,2,2 \}\; (B=7, q=2)$

We can use $2B + 2$ distinct colors and build a coloring game instance on a $2B + 2 + 1 = 17 \times 1$ grid like in the figure.

enter image description here

$\endgroup$
  • $\begingroup$ thanks for the comments! For the 1xn case I fail to see why it is NP complete. Reduction to directed reachability: Create vertices $v(a,x,y)$ for each $a \in [n-1]$, each color $x \in M_{1a}$ and $y\in M_{1(a+1)}$ such that $(x,y)\in H_{1a}$. Now connect a vertex $v(a,x, y)$ to $v(a+1,z,w)$ if and only if $y=z$. Then add a source vertex $s$ connected to all vertices $v(1,x,y)$ and a target vertex $t$ connected to all vertices $v(n-1,x,y)$. We have a solution if and only if there is a directed path from $s$ to $t$. The size of the graph is polynomial in $|\Sigma|$. $\endgroup$ – Mateus de Oliveira Oliveira Nov 28 '17 at 19:58
  • $\begingroup$ @MateusdeOliveiraOliveira: I'll add a "colorful" example of the $n \times 1$ case tomorrow! $\endgroup$ – Marzio De Biasi Nov 28 '17 at 20:46
  • $\begingroup$ @MarzioDeBiazi, in the graph constructed in my previous comment, there is a path $s,v(1,x_1,x_2)v(2,x_2,x_3)...v(n-1,x_n-1,x_n), t$ if and only if $x_1x_2...x_n$ is a $1xn$ matrix with $x_j\in M_{1j}$ for each $j\in [n]$ and $(x_j,x_{j+1})\in H_{1j}$ for each $j\in [n-1]$. Therefore, either you're claiming that $NP = NL$ or we are speaking about distinct problems. Note that I'm writing $1xn$ matrix to denote a matrix with $1$ row and $n$ columns. And that the set of colors $\Sigma$ is given as a list in the input, and in particular I'm assuming that $\Sigma = n^{O(1)}$. $\endgroup$ – Mateus de Oliveira Oliveira Nov 28 '17 at 21:57
  • $\begingroup$ @MateusdeOliveiraOliveira: you are right: while drawing the example for the nx1 case I found that, in order to be NP-complete, you must also add the constraint that each color is used only once (and the problem becomes less interesting). $\endgroup$ – Marzio De Biasi Nov 29 '17 at 7:42
  • $\begingroup$ @MateusdeOliveiraOliveira: if you are interested I also found a proof that your problem is NPC even with fixed 4 colors ($|\Sigma| = 4$) $\endgroup$ – Marzio De Biasi Dec 1 '17 at 8:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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