Reconfiguration of Unit Squares and Disks: PSPACE-Hardness in Simple Settings

As a preliminary step we provide a helpful tool for verifying the correctness of the reduction. Let $P$ be a grid polygon. A set $ℛ$ of $k$ non-overlapping $4\times 4$ squares, each contained in $P$, is called a set of reference centers for $P$ if, for any packing of $k$ $8\times 8$ squares in $P$, each square in the packing contains one square in $ℛ$. Such a configuration of $8\times 8$ squares in $P$ is called perfect. For every $y\in \mathbb{Z}$, let $b_y$ be an integer in $[0,8)$. For $x,y\in \mathbb{Z}$, let $S_{xy}=[8x+b_y,8x+b_y+4]\times [8y,8y+4]$. Suppose that each $S_{xy}$ is either fully contained in $P$ or is interior-disjoint with $P$. Let $ℛ$ be the set of those $S_{xy}$ that are fully contained in $P$. An example is shown in Figure 3. We will show that $ℛ$ is a set of reference centers for $P$.

By Lemma 7, in any reconfiguration from one perfect configuration to another, each square contains the same reference center the whole time, i.e., the squares merely shift slightly sideways and up and down around the same reference center. In order to describe the mechanics of our intended reconfigurations, we only need to consider positions of squares that are extreme or centered in each direction with respect to their reference centers. This leaves us with the nine possible positions shown in Figure 4(a). In Section 3.7, we prove that also arbitrary continuous reconfigurations in $P$ correspond to reconfigurations of $\varphi$, but for understanding the key ideas of the reduction, it suffices to consider these nine discrete positions.

When the top (resp. bottom) edge of a square aligns with that of its reference center, we say that the square is down (resp. up). Otherwise, the midpoints of the reference center and the square have the same $y$-coordinate, in which case we say that the square is vemid (abbreviation of vertically in the middle). When the left (resp. right) edge of the square aligns with that of the reference center, the square is right (resp. left). Otherwise, the midpoints of the reference center and the square have the same $x$-coordinate, in which case we say that the square is homid (abbreviation of horizontally in the middle).

For most squares, several of the nine possible positions can be excluded, for instance due to being pushed by the boundary of $P$ or another square. In our figures, we use a color scheme for the reference centers, to make the reader aware of what possible positions a square has. The colors have the following meanings: the square can not move (pink), only move vertically (orange), only move horizontally (green), move vertically and horizontally (brown). There might exist additional restrictions on the positions that are not indicated by the colors.

On a big scale, our construction follows the ideas of Abrahamsen and Stade [1]. Therefore, we start by reviewing the high level ideas. Let $\varphi$ be an instance of Monotone-Planar-3-Sat with variables $x_1,\mathrm{\dots },x_k$ and consider the variable-clause-incidence graph $G$ with a suitable embedding. We now describe schematically the construction of a grid polygon $P$. Each feasible solution to $\varphi$ corresponds to a configuration of $8\times 8$ squares in $P$, and there is a reconfiguration between two configurations if and only if there is a reconfiguration between the two solutions of $\varphi$.

In the first step, we introduce a segment representation that consists of horizontal segments for vertices and clauses, and of vertical segments for the edges of $G$, see in Figure 5(b). The idea behind this representation is as follows: The horizontal segments will correspond to one or several rows of squares which transmit information horizontally. Similarly, the vertical segments will correspond to columns of squares that transmit information vertically. The endpoints of each segment should be on the outer face of the drawing, so that the smallest enclosing orthogonal polygon runs through all of the endpoints.

To construct the segment representation, we introduce a horizontal segment for each variable $x_1,\mathrm{\dots },x_k$ in this order bottom-up, where the $x$-coordinates of the left and right endpoints are increasing, see Figure 5. Furthermore, the right endpoint of $x_1$ is to the right of the left endpoint of $x_k$, so that all the segments have a common horizontal overlap. These are the primary variable rows. The positive clauses are represented by horizontal segments above $x_k$ and the negative clauses by horizontal segments below $x_1$. We say that a clause $c^{\prime }$ is nested in a clause $c$, if in $G$ the clause node of $c^{\prime }$ lies inside a cycle defined by two incident edges of the node of $c$ closed with a path between variable nodes. For instance, in Figure 5(a), $c_2$ and $c_3$ are nested inside $c_1$. Note that the property of being nested defines a partial order. If a positive clause $c_i$ is nested inside $c_j$, then we place the segment of $c_i$ above that of $c_j$ in the segment representation. If instead the clauses are negative, the segment of $c_i$ is below that of $c_j$. Each edge $x_i{c}_j$ of $G$ is realized by a vertical segment connecting the segments of $x_i$ and $c_j$. All vertical segments to the positive clauses are placed to the right of all those to the negative clauses. The left-to-right ordering of the edges to the positive clauses along the variables $x_1,\mathrm{\dots },x_k$ in $G$ is preserved by the corresponding vertical segments, as well as the ordering of the edges to the negative clauses. The segment of a positive (resp. negative) clause $c_j$ starts at the top (resp. bottom) endpoint of the vertical segment corresponding to the leftmost edge incident to $c_j$ in $G$ and ends at the top (resp. bottom) endpoint of the rightmost edge.

In the next step, illustrated in Figure 5(c), we replace each clause segment by three auxiliary variable segments, one for each of the variables connected to the clause. In the right side of the auxiliary segments, we connect them using vertical segments to an OR gadget, represented by a red horizontal segment. As sketched in the figure, we construct (guided by the partial nested-order of the positive and negative clauses) a polygon whose boundary approximately follows the outer face of the resulting representation, but the finer details will be given later. The following lemma was proved in [1].

Algebraically, the introduction of an auxiliary variable row for a clause $c_t$ corresponds to the following equivalence:

Here, $x_i,x_j,x_k$ are the primary (original) variables and $y_{t,i},y_{t,j},y_{t,k}$ are the auxiliary variables introduced for that particular clause. We remark that the formula is not monotone anymore, but the only non-monotone clauses are implications. Note that the equivalence also preserves reconfiguration: If, say, $x_i$ changes to false, then we change $y_{t,i}$ to false before changing $x_i$. If $x_i$ changes to true, then we change $y_{t,i}$ to true after $x_i$. For a negative clause $c_t$ , we use an analogous equivalence:

We informally distinguish between gadgets and components in our constructions, where a gadget is given by a set of segments on the boundary creating some simple functionality, and a component is thought of as a whole region of the polygon that can involve an arbitrary number of gadgets.

On a very high level the truth assignment of a variable of $\varphi$ is encoded by a configuration of a so-called variable component; see Figure 6. The variable component (used to represent primary and auxiliary variables) has essentially three possible states, namely plus, minus and transitional. The first two correspond to the values true and false of a binary variable, while the truth value of the transitional state is defined to be the true/false value of the previous plus/minus state. In order to split the information represented in a variable component of a primary variable and transfer it to a variable component of an auxiliary variable we use PUSH gadgets. In particular, these gadgets are used to model the implication-clauses and they come in two versions: PUSH-UP-IF-MINUS and PUSH-DOWN-IF-PLUS. The former is used to model implications of the form $y\Rightarrow x$, the later for $\neg y\Rightarrow \neg x$. The gadgets use a vertically moving stack of square rows with growing width (called pyramid) to transmit information from primary to auxiliary variables, see for example Figure 8. For a PUSH-UP-IF-MINUS gadget representing an implication $y\Rightarrow x$ a pyramid that is raised enforces that the auxiliary variable component of $y$ is set to minus, if the variable component of $x$ is set to minus. Similarly, a PUSH-DOWN-IF-PLUS gadget modeling $\neg y\Rightarrow \neg x$ has the functionality that a pyramid that is lowered enforces that the auxiliary variable component of $y$ is set to plus, if the variable component of $x$ is set to plus. We will make sure that the vertically moving pyramid structure do not collide with the vertically operating variable components they “cross”. To only allow satisfying assignments for every clause we place an OR gadget that is connected with the corresponding auxiliary variable components. We reuse the ideas for the PUSH Gadgets. For a clause $(y_i\vee y_j\vee y_k)$ the auxiliary variables will push a pyramid up into the clause gadget if the corresponding auxiliary variable is set to minus. The OR gadget has only room for two of these pyramids to push up. The clauses $(\neg y_i\vee \neg y_j\vee \neg y_k)$ are handled symmetrically. Here, an auxiliary variable set to plus would result in a pyramid pushing down and the OR gadget can only incorporate two lowered pyramids.

We continue with describing the gadgets and components in detail.

The variable component has two main rows of squares and an arbitrary number of PUSH gadgets, ensuring dependency between the primary and auxiliary variables and between the auxiliary variables and the OR gadgets. The PUSH gadgets require the introduction of helper rows padded along the main rows, above the top row or below the bottom row. The construction of PUSH gadgets and helper rows will be explained in later sections.

The construction of the main rows of a variable component is shown in Figure 6. A perfect configuration of the component has three possible states, as defined by the horizontal position of the two rightmost squares (covering the brown reference centers). Note that none of the two squares can push right, and if one is homid, the other needs to be right.

If the bottom is in the homid position, the state is plus. If the top is in the homid position, the state is minus. Otherwise, the state is transitional.

Now we describe what happens when a block of raised or lowered squares “crosses” a variable component. As discussed before, pyramids made of such blocks are used to create dependencies between two variable components, but it is important that they can cross other variable components without interacting with them.

When a stack of raised squares crosses a row of squares with a different horizontal alignment, the stack of raised squares will grow in width. Hence, the stack will be pyramid shaped if all rows have a different alignment than the neighboring rows. It is important that we know the width of a pyramid when it reaches the target variable component where it will end. Thus, we need to know exactly how many times the width is increased and which squares are raised in the top row. To this end, and in order to create a necessary amount of vertical spacing, we introduce static rows in between all neighboring pairs of variable components. A static row consists of squares in the beginning and in the end, which cannot move, and some squares in the middle, which can move vertically up and down, see Figure 7.

So in particular, all squares in a static row have a fixed horizontal position.

We ensure that the fixed horizontal position is never aligned with the rows of the variable component. Furthermore, the top row of a variable component is never aligned with the bottom row, see Figure 8. Hence, when a pyramid crosses a variable component, the specific horizontal positions of the rows do not affect which squares are raised/lowered on the other side of the variable. This is expressed in the following lemma.

Recall that there may be helper rows above or below the main rows of a variable component, which will be explained in more detail in Section 3.5. Conceivably, these could be unaligned with the main rows, which would cause a pyramid to grow more in width when crossing the variable. However, if they are aligned (which is our “intended behavior” of the helper rows), then the width will not grow beyond what is expressed by Lemma 9.

Figures 9 and 10 show the PUSH-UP-IF-MINUS and PUSH-DOWN-IF-PLUS gadgets, respectively. The gadgets are mirror images of each other by a horizontal axis. In order to make PUSH gadgets, we need a square that is pushed up or down only when it is left. To this end, we introduce helper rows, which are extra rows above and below the main variable rows. Consider the PUSH-UP-IF-MINUS gadget, shown in Figure 9. If the squares of the lower main row are left, the squares of the helper row will be left as well, because the square $a$ presses down $b$, which thus pushes $c$ to the left. Therefore the square $d$ will be up, and a pyramid of raised squares is created.

The PUSH-DOWN-IF-PLUS gadget works by analogous mechanics. If the squares in the upper main row are left, two squares of the lower row are pushed down, see Figure 10.

All helper rows are created at the right end of the variable gadget and end at a PUSH gadget. Figure 11 shows schematically where the helper rows are placed, and Figure 12 shows a detailed example with multiple helper rows. Note that with multiple helper rows, the same principle is used as with a single helper row in order to ensure that when the lower main row is left, then all helper rows below are also left, so they all create pyramids of raised squares.

We now describe how a pyramid ends at an auxiliary variable component; see Figure 13 for a concrete example to support the description. When we make a PUSH-UP-IF-MINUS gadget from a primary variable $x$ to an auxiliary variable $y$, we create a pocket in the boundary of $P$ along the upper primary row of $y$ to enable the squares of the pyramid to raise. We place the pocket so that the squares can only raise if they are homid (and if the pyramid has grown in width by exactly three squares every time it crossed another variable component). Thus, the rightmost square of the top row of $y$ is also homid, so $y$ must be minus. We have thus made the implication $y\Rightarrow x$.

In minus, pyramids are created to the positive auxiliary variables, which in turn create pyramids to the positive clauses. Likewise, in plus, pyramids are created to the negative clauses. In transitional, pyramids are created to all clauses. As we will see in Section 3.6, there will only be room for two pyramids for each clause. Hence, each clause ensures that one of the variables is in the plus/minus state that represents the true/false value that satisfies the clause. This gives the following lemma.

Figure 14 shows the positive OR gadget. The gadget is connected to three auxiliary variable components. Using PUSH-UP-IF-MINUS gadgets, pyramids can raise from the variables and end in the OR gadget. The gadget allows for two pyramids to be raised, but not all three at once. Hence, one variable must be plus. When at most one pyramid is raised, the squares in the top of the gadget can reconfigure so that there is room for any of the other two pyramids to raise. An example is shown in the figure – the reader can easily check that it is likewise possible in the other five cases where one pyramid is raised and we need to make room for one of the other two to raise as well. This corresponds to a reconfiguration of the formula $\varphi$: If $x\vee y\vee z$ is a clause and one of the variables, say $z$, changes from positive to negative, then $x$ or $y$ must have been positive before $z$ changes (otherwise the clause would not be satisfied after $z$ changing). Hence, there was only one pyramid, so the squares in the gadget can reconfigure to accommodate raising the pyramid from $z$.

Figure 15 shows how the OR gadget is connected to the variable components. The negative OR gadget is obtained by reflection along a horizontal axis.

Recall that we start with a Monotone-Planar-3-Sat formula $\varphi$ and two satisfying assignments ${\sigma }_0$ and ${\sigma }_1$ of $\varphi$. In our reduction, we create a polygon $P$ as described. We define start and target configurations $c_0$ and $c_1$ according to ${\sigma }_0$ and ${\sigma }_1$: We place squares in all primary and auxiliary variable components in $c_i$ in the plus/minus state corresponding to the value of the variable in ${\sigma }_i$. By construction there is room for the pyramids created by PUSH gadgets. We now need to verify that there is a reconfiguration between ${\sigma }_0$ and ${\sigma }_1$ in $\varphi$ if and only if there is one between $c_0$ and $c_1$ in $P$. This is expressed by the following two lemmas.

Finally, we prove the containment in $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$.

Theorem 2 result now follows from Theorems 1, 12, 13, and 14.

As we only consider perfect configurations in our reduction, by Lemma 7 each square always contains its reference center. Thus, we can easily label each square and obtain hardness for the labeled variant, i.e., Corollary 3.