Finding Shortest Walks in Kuru Kuru Kururin

Recall that $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}=\mathrm{𝖭𝖯𝖲𝖯𝖠𝖢𝖤}$ from Savitch’s theorem [25]. So, if there exists a valid base helirin walk $𝒲=({𝒮}_0,t_0,({\mu }_1,d_1),\mathrm{\dots },({\mu }_k,d_k))$, we can find it by guessing moves $({\mu }_i,d_i)$ in order, performing them on-the-fly while checking the validity of the corresponding walk prefixes. We do so while keeping track of the current base helirin state, and of time with a non-negative integer variable, checking that it never goes above $D$. $◀$

Next, we show that the base problem is $\mathrm{𝖭𝖯}$-hard, regardless of the value of the angular speed.

We reduce from weakly $\mathrm{𝖭𝖯}$-hard problem SubsetSum [12]. We take inspiration from the $\mathrm{𝖭𝖯}$-hardness proof of problem RestlessForemostTemporalWalk on interval temporal graphs by Zeitz [29]. Let $a_1,\mathrm{\dots },a_n$ be the elements and let $B$ be the target. Let $A={\sum }_{1\le i\le n}{a}_i$ and $L=2A+1$.

We propose the following instance of BaseKururin. We set the helirin properties to $(\mathrm{\ell },{\nu }_{card},{\nu }_{diag},\omega )=(L,2L,2L-1,0)$. We set $D=2A+n-1$ and ${𝒮}_0=(L,L,1/2,1)$. We set wall tiles to form the instance illustrated in Figure 7. For each choice of element $a_i$ in SubsetSum, we have two branching paths: one, which we call $P_{i,0}$, where you go east for $2a_i$ time units, and another, which we call $P_{i,1}$, where you go north-east for $a_i$ time units, then south-east for $a_i$ time units. Both paths are then merged. Finally, there is a single $1\times 1$ goal tile at position $((2D+1)L-2B,L)$.

Recall that . As such, by only taking paths of the form $P_{i,0}$, we only have access to $x$-coordinates which are multiples of $L$. So, the goal tile can only be reached by some taking paths of the form $P_{i,1}$, each of which induces an $x$-coordinate offset of $(-2a_i)$ modulo $L$.

If our instance of SubsetSum has a solution $S\subseteq \{1,\mathrm{\dots },n\}$, we propose base helirin walk $𝒲$ where, for all $i\in \{1,\mathrm{\dots },n\}$, we take path $P_{i,1}$ if $i\in S$ and path $P_{i,0}$ otherwise. This walk is valid and ends at position $((2D+1)L-2({\sum }_{i\in S}{a}_i),L)=((2D+1)L-2B,L)$. Conversely, if we have a valid base helirin walk $𝒲$, by our choice for speed values ${\nu }_{card},{\nu }_{diag}$ and time $D$, only the east, north-east and south-east directions can be used. Therefore, according to the position of wall tiles, the underlying path from base helirin walk $𝒲$ is necessarily of the form $P_{i,j_1}\mathrm{\cdots }{P}_{n,j_n}$ with $j_i\in \{0,1\}$ for all $i$. We propose $S=\{i\in \{1,\mathrm{\dots },n\}|j_i=1\}$. Then, because $𝒲$ is valid and ends at position $((2D+1)L-2B,L)$, we have: $2B=2({\sum }_{i\in S}{a}_i)$. $◀$

Note that the idea behind this reduction would work with any angular speed $\omega$: it purely relies on the offset between cardinal and diagonal speed values, which gets magnified over time. As such, time $D$ needs to be encoded in binary for our reduction to work. In fact, if time $D$ is given in unary in the input, then BaseKururin can be solved in polynomial time.

We show this by encoding our instance as a point temporal graph with $𝒪(D^4)$ vertices and $𝒪(D^5)$ timed arcs. Each accessible center position can be encoded as a tuple $(n_N,n_{NE},n_E,n_{SE})$ of values in $\{-D,\mathrm{\dots },D\}$ giving a signed number of unit-time base moves in each direction in order to reach it. And timed arcs are of the form $(u,v,t,1)$, where $u$ represents a center position accessible at time $t$ and $v$ represents a center position accessible from $u$ with one of the nine unit-time base moves. If $N$ is the number of tiles in our instance $I$ of BaseKururin then, in $𝒪(D^{5}N)$ time, we can compute all accessible center positions, including whether they are in a goal tile, and compute an equivalent point temporal graph ${𝒢}_I$. Then problem ForemostTemporalWalk can be solved in linear time on ${𝒢}_I$ to look for a walk from the starting center position to all accessible center positions in goal zones simultaneously [4]. $◀$

Additionally, in the proof of Theorem 17, note that wall tiles were crucial to enforce specific durations for the diagonal base moves which corresponded to the elements in the instance of SubsetSum. If there are no such walls then, for each goal tile, one can compute a base helirin walk reaching it in minimum duration via an integer linear program with a constant number of variables and constraints. We have eight non-negative integer variables indicating the number of unit-time base moves in each of the eight directions. We aim to minimize their sum while ending the walk in the square goal tile (i.e., with four constraints). Each system can be solved in $𝒪(1)$ time (e.g., see [1]), so we can solve our problem in $𝒪(N)$ time. Details are available in Appendix A.3.

We reduce from weakly $\mathrm{𝖭𝖯}$-hard problem SubsetSum [12]. Let $a_1,\mathrm{\dots },a_n$ be the elements and let $B$ be the target. Let $A={\sum }_{1\le i\le n}{a}_i$ and $L=16(A+2n+1)$.

We propose a similar reduction to the proof of Theorem 17, except we rely on rotation angle offsets instead of position offsets. We set $D=6n+1,$ $q_{\omega }=L/2$ and $p_{\omega }=1+q_{\omega }/8$. We set the helirin properties to $(\mathrm{\ell },{\nu }_{card},{\nu }_{diag},\omega )=(L,2L,0,p_{\omega }/q_{\omega })$ and we set ${𝒮}_0=(L,L,0,1)$. We set wall tiles to form the instance illustrated in Figure 8. For each choice of element $a_i$ in SubsetSum, we have two branching paths: one, which we call $P_{i,0}$, where you go south, then east for $2$ time units, then north, and another, which we call $P_{i,1}$, where you go north, then east for $2$ time units, then south. Both paths are then merged. Plus, there is a single $2L\times 2L$ goal tile at position $((4n+1)2L,0)$.

Now, let $𝒫=\{0,\mathrm{\dots },q_{\omega }/2\}$. Given $p\in 𝒫$, let $(x_p,y_p)$ be the coordinates of the right extremity of the helirin at angle $p\pi /q_{\omega }$. Since $L>2q_{\omega }/\sqrt{2}$, function $(p\mapsto (x_p,y_p))$ is injective over $𝒫$, and sequences ${(x_p)}_{p\in 𝒫}$ and ${(y_p)}_{p\in 𝒫}$ are respectively non-increasing and non-decreasing. Plus, for each $p\in 𝒫$, couple $(x_p,y_p)$ is merely a rational approximation of the cosine and sine of angle $p\pi /q_{\omega }$, and thus can be computed in polynomial time.

Knowing this, we can use these values to position our spring tiles accordingly. In bottom paths $P_{i,0}$, we rely on numerator $(p=q_{\omega }/4+1)$ to align the edges with the mirroring property. In bottom paths $P_{i,1}$, we rely on numerator $(p=q_{\omega }/4+1-a_i)$ instead. And, once both paths are merged, we rely on numerator $(p=-q_{\omega }/8)$. Finally, right before the goal tile, we set two wall tiles in order to block positions $(x_p,y_p)$ for every $p\in 𝒫\backslash \{B+2n\}$. Then the correspondence between valid base helirin walks and solutions of the SubsetSum instance unfolds similarly to the proof of Theorem 17. Finally, one can easily adapt the reduction to case ${\nu }_{diag}={\nu }_{card}$. $◀$

Still, the algorithm from Theorem 19 can be adapted if, on top of time $D$, the denominator $q_{\omega }$ of angular speed factor $\omega$ is given in unary in the input. Then the number of vertices in the equivalent point temporal graph is in $𝒪(D^4{q}_{\omega })$.

We focus on the $\mathrm{𝖭𝖯}$-hardness proof with spiked balls and ${\nu }_{diag}=0$. All other proofs are discussed in Appendix A.5.

We reduce from 3-Sat. Let $\phi ={\bigwedge }_{1\le i\le m}(l_{i,1}\vee l_{i,2}\vee l_{i,3})$ be a 3-CNF formula with $m$ clauses and $n$ variables, w.l.o.g. with exactly three literals per clause. We set the helirin properties to $(\mathrm{\ell },{\nu }_{card},{\nu }_{diag},\omega )=(1,2,0,0)$ and base helirin state ${𝒮}_0$ to $(x,y,\alpha ,b)=(1,1,0,0)$. Plus, all spiked balls will have radius $1$, $\mu =\mathrm{\varnothing }$ in their base move, and $\nu =1$. So, all relevant elements will be set along a grid of $2\times 2$ squares.

We encode the formula as an obstacle course going from left to right. Figure 9 represents the base layout, which can be easily obtained with square wall tiles. Each vertical layer represents a clause and has three available ways, each associated to a literal in this clause. And we set a single goal tile of side length $2$ at $(x,y)=(4m+4,0)$. Then, going from the start area (in red) to the goal tile (in yellow) with no wait takes time at most $T=6m+6$.

The plan is to dedicate time $T$ for each of the $2^n$ valuations of the variables to give them a chance to reach the goal tile from the start, which will correspond to making $\phi$ true. First, we only allow the helirin to leave the start area at periodic times $(1modT)$. We do so with a spiked ball at $(x,y)=(2,0)$ with $\tau =T,t_0=2$ and $d=T-1$. Plus, once the helirin leaves the start area, we force it to reach the goal tile by the end of the time period. We do so by setting spiked balls for every $2\le i\le 2m+2$ and $0\le j\le 4$ at $(x,y)=(2i,2j)$ with $\tau =T,t_0=0$ and $d=1$.

Now, for $1\le k\le n$ we tie variable $x_k$ to spiked balls of time period $\tau =T{2}^k$. More precisely, given $1\le i\le m$ and $1\le j\le 3$, we set a spiked ball $S_{i,j}$ at $x=4i+2$ and $y=4j-4$, with move duration $d=T{2}^{k-1}$ and:

• $\mathrm{■}$

  if $l_{i,j}=x_k$ is a positive literal: $\tau =T{2}^k,t_0=0,d=T{2}^{k-1}$,

• $\mathrm{■}$

  if $l_{i,j}=\neg x_k$ is a negative literal: $\tau =T{2}^k,t_0=d=T{2}^{k-1}$.

In other words, spiked balls tied to literal $x_k$ (resp. $\neg x_k$) block their respective path during periodic times $(0,\mathrm{\dots },T{2}^{k-1}-1modT{2}^k)$ (resp. $(T{2}^{k-1},\mathrm{\dots },T{2}^k-1modT{2}^k)$).

We now piece everything together. Let us consider valuations $(x_n,\mathrm{\dots },x_1)$ by lexicographic order. Given $0\le h\le 2^n-1$, let $v_h$ be the $h^{th}$ valuation by lexicographic order. Then, $v_h$ matches with the binary representation of $h$ from the right (e.g., the value of $x_1$ in $v_h$ is the last digit). Knowing this, consider time units $Th,\mathrm{\dots },T(h+1)-1$. During them, by the definition of spiked balls $S_{i,j}$, the latter block their respective path if and only if:

• $\mathrm{■}$

  $l_{i,j}=x_k$ and the ${(k-1)}^{th}$ digit of $h$ from the right is $0$, or

• $\mathrm{■}$

  $l_{i,j}=\neg x_k$ and the ${(k-1)}^{th}$ digit of $h$ from the right is $1$.

Thus the missing spiked balls $S_{i,j}$ exactly correspond to the literals which are made true by valuation $v_h$. As a result, starting from time $Th$, we can reach the goal tile by time $T(h+1)$ if and only if $v_h$ makes $\phi$ true. Finally, we have that $\phi$ is satisfiable if and only if, starting from base helirin state ${𝒮}_0$, there is a base helirin walk reaching the goal tile by time $D=T{2}^n$. $◀$