Token Sliding Reconfiguration on DAGs

In this paper, we consider directed graphs and allow tokens to only slide in the direction of the edges. Note, that token jumping is not well suited for directed graphs, as arbitrary jumps stay the same in the directed setting. So far very little is known for directed graph’s reconfiguration. Recently, Ito et al. [11, Theorem 2] proved that Independent Set Reconfiguration for Directed Token Sliding (ISR-DTS) is $\mathrm{𝖭𝖯}$-hard on DAGs and $𝖶$[1]-hard when parameterized by the number of tokens. On the tractable side of things, they show that it is linear time solvable on orientation of trees [11, Theorem 3]. The hardness extends to $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-completeness for oriented planar graphs, split graphs, bipartite graphs and most noticeably bounded treewidth graphs [1].

We improve on both the side of hardness, as well as the side of tractability. We first look at the depth of the DAGs and provide sharp dichotomy in both the classical and parameterized setting. In the following statements, $k$ refers to the number of tokens.

Additionally, we show that a combination of the parameters $k$ and treewidth leads to tractability in DAGs. We do so by adapting the recently developed framework of galactic reconfiguration [3] to directed graphs. The following result can be considered our main contribution.

Finally, we go back to undirected graph, introduce a new parameter (the iteration $\iota$) that measures the maximum number of times a specific token can enter a specific vertex.

These results for graphs of bounded treewidth is a step toward solving one of the most prominent open problem in this line of work (see [6, Question 5]): is ISR-TS $\mathrm{𝖥𝖯𝖳}$ when parameterized by $k$ and the treewidth of the graph?

The previous best algorithms only work on the more restricted class of bounded treedepth [9], or require to also parameterize by the length $\mathrm{\ell }$ of the reconfiguration sequence [15]. In comparison, our new parameter iteration is much smaller than the length of the reconfiguration sequence. In terms of techniques, parameterizing by $\mathrm{\ell }$ enabled the authors of [15] to reduce to the model checking problem for $\mathrm{𝖬𝖲𝖮}$ formula which is solved using Courcelle’s Theorem. In our case, we do not believe that we can reduce to Courcelle’s theorem. Thus, the presented algorithm is the first to use dynamic programming on graph of bounded treewidth “by hand” for Independent Set Reconfiguration.

The rest of the paper is structured as follows. Section 2 provides the required background and fixes notations. Section 3 is devoted to efficient algorithms and the proof of Theorem 1.1. The proof of Theorem 1.2 is provided in Section 4, followed by the proof of Theorem 1.3 in Section 5. In Section 6 we introduce additional notions around galactic reconfiguration for our main algorithm in order to prove Theorem 1.4. Finally, in Section 7 we discuss implications for undirected graphs, and Theorem 1.5.

We use standard graph notations. All graphs are directed and loop-free unless stated otherwise. Unless preferable for readability we abbreviate an edge $(u,v)$ with $uv$. We denote the open out-neighborhood of a vertex $v$ with $N^{+}(v)$ and the open in-neighborhood with $N^{-}(v)$. A graph without cycles is called a DAG. The depth of a DAG is the number of vertices on its longest directed path. Note that if a DAG has depth $d$, then its vertices can be grouped in $d$ levels with every edge going from a vertex at some level to a vertex at a greater level. One can inductively define the first layer as the vertices of in-degree 0, and the $i$th layer as the vertices whose entire in-neighborhood is in smaller levels.

For a directed graph $G$, the underling undirected graph is obtained by disregarding the edge direction and removing all double edges. That is the graph $(V(G),\{\{u,v\}\mid uv\in E(G)\text{ or }vu\in E\})$. A set of vertices of a directed or undirected graph is called independent if the vertices are pairwise nonadjacent.

In the parameterized framework, a problem is said to be fixed parameter tractable ($\mathrm{𝖥𝖯𝖳}$), if there exists an algorithm that solves it in time $f(k)\cdot n^c$ for a computable function $f$ and constant $c$. An alternative characterization of $\mathrm{𝖥𝖯𝖳}$ is through the existence of a kernel, that is polynomial time computable function that maps each instance to an instance of size $g(k)$ for some computable function $g$. The returned instance should be a positive-instance exactly if the inputted instance is. Kernels are commonly presented in the form of data reduction rules, that provide instructions on how to shrink the size of the input.

Under commonly made assumptions, problems that are $𝖶[1]$-hard are considered not to be $\mathrm{𝖥𝖯𝖳}$. Similar to $\mathrm{𝖭𝖯}$-completeness, we use $\mathrm{𝖥𝖯𝖳}$-reductions to transfer hardness. However, these reductions may use a longer $\mathrm{𝖥𝖯𝖳}$ running time but are more restricted in the sense that the parameter of the resulting instance may not depend on the size but only on the parameter of the inputted instance. More background on $\mathrm{𝖥𝖯𝖳}$ algorithms and $\mathrm{𝖥𝖯𝖳}$-reduction can be found in the book [7].

A configuration ${\alpha }_i$ is a function from a set of tokens $T=\{t_1,t_2,\mathrm{\dots },t_k\}$ to the set of vertices $V$.

For two independent sets $S$ and $D$ of size $k$ in a graph $G$, a reconfiguration-sequence for ISR-DTS is a sequence of configurations ${({\alpha }_i)}_{i\in I}$ such that:

1. 1.

   ${\alpha }_1(T)=S$ and ${\alpha }_{|I|}(T)=D$.

2. 2.

   For every $i\in I$, and for distinct tokens $t$ and $t^{\prime }$: ${\alpha }_i(t)\ne {\alpha }_i(t^{\prime })$.

3. 3.

   For every $i\in I$, and for distinct tokens $t$ and $t^{\prime }$: $({\alpha }_i(t),{\alpha }_i(t^{\prime }))\notin E(G)$.

4. 4.

   If ${\alpha }_i(t)\ne {\alpha }_{i+1}(t)$, then there exists an edge $({\alpha }_i(t),{\alpha }_{i+1}(t))\in E(G)$ and for every other token $t^{\prime }\ne t$ it holds that ${\alpha }_i(t^{\prime })={\alpha }_{i+1}(t^{\prime })$.

We generally assume that $I$ is a sequence from 1 to $|I|$. For a configuration ${\alpha }_i$ we call all configurations ${\alpha }_j$ succeeding or a successor, if $j>i$. If $j=i+1$ we say that it is a direct successor.

Let $t$ be a token and $\alpha ={({\alpha }_i)}_{i\in I}$ a sequence with ${\alpha }_1(t)=u$ and ${\alpha }_{|I|}(t)=v$. We say that the token $t$ comes from $u$ and ends up in $v$. Similarly we say that a token comes from a subgraph $A$ and ends up in a subgraph $B$ if ${\alpha }_1(t)\in V(A)$ and ${\alpha }_{|I|}(t)\in V(B)$. Additionally, if there is a token on $v$ we say that this token blocks all $u\in N(v)$.

Galactic graphs were recently developed to prove that ISR-TS is in $\mathrm{𝖥𝖯𝖳}$ for undirected graphs of bounded degree [3]. We restate their definition, slightly adapted for directed graphs. A galactic graph is a graph where the vertex set is partitioned $V(G)=A(G)\cup B(G)$ into planets $A(G)$ and black holes $B(G)$.

For a (galactic) graph $G$ and a subsets of its vertices $V^{\prime }$ we say that it collapses to $G^{\prime }$ if $G-V^{\prime }=G^{\prime }-b$ with $b\in B(G^{\prime })$ and $G^{\prime }$ contains an edge $(u,b)$ (respectively $(b,u)$) if $G$ contains an edge $(u,v)$ (respectively $(v,u)$) for some $v\in V^{\prime }$. We denote this graph with $G\odot V^{\prime }$. For the empty set, we define $G\odot \mathrm{\varnothing }=G$. Intuitively, this operation takes a set of vertices (planets and black holes) and merges them into one black hole.

Note, that this operation takes a graph on the left-hand site and a vertex set on the right-hand site. Thus, multiple applications of this operator are left-associative.

We will assume that the black holes are named (or labeled) in such a way that they are uniquely identified by the planets that collapsed into it in the original graph. Meaning that for example for disjoint $V_1,V_2$ it holds $G\odot V_1\odot V_2\odot \{b_1,b_2\}=G\odot V_1\cup V_2$, where $b_1$ and $b_2$ are the black holes created when collapsing $V_1$ and $V_2$ respectively. This can be realized by representing planets as sets containing a single element and black holes as the union of the sets representing vertices (planets or black holes) with an additional marker for black holes added.

For two multisets $S$ and $D$ of size $k$ in a graph $G$, a galactic reconfiguration sequence for ISR-DTS is a sequence of configurations ${({\alpha }_i)}_{i\in I}$. Where ${\alpha }_i$ is a function from a set of tokens $T=\{t_1,t_2,\mathrm{\dots },t_k\}$ to $V$, such that:

1. 1.

   ${\alpha }_1(T)=S$ and ${\alpha }_{|I|}(T)=D$.

2. 2.

   For distinct tokens $t$ and $t^{\prime }$: ${\alpha }_i(t)\ne {\alpha }_i(t^{\prime })$ or ${\alpha }_i(t)\in B(G)$.

3. 3.

   All ${\alpha }_1(T)\cap A(G),\mathrm{\dots },{\alpha }_{\mathrm{\ell }}(T)\cap A(G)$ are independent sets.

4. 4.

   If ${\alpha }_i(t)\ne {\alpha }_{i+1}(t)$, then there exists an edge $({\alpha }_i(t),{\alpha }_{i+1}(t))\in E(G)$ and for every other token $t^{\prime }\ne t$ it holds ${\alpha }_i(t^{\prime })={\alpha }_{i+1}(t^{\prime })$.

Note that in a galactic reconfiguration sequence, several tokens are allowed to be on the same vertex (including for the first and last configuration), as long as this vertex is a black hole. When we collapse an instance for ISR-DTS and the collapsed vertex set contains start and end positions, we generally assume that these positions in their multiplicity get assigned to the created black hole.

Note that in the above definition, ${({\beta }_j)}_{j\in J}$ is a valid reconfiguration sequence, i.e. the tokens only slide along edges and are only on neighboring vertices if at least one of them is a black hole. Furthermore, form this definition, it might look like a single reconfiguration sequence can collapse to multiple sequences on the same graph (depending on the chain of collapses). We later show in Lemma 6.1 that it is not the case, and the collapse notion (with several successive collapses) is therefore well-defined.

A tree decomposition of a undirected graph $G$ is a pair $𝒯=(T,\mathrm{𝖻𝖺𝗀})$ where $T$ is a rooted tree and $\mathrm{𝖻𝖺𝗀}:V(T)\to 2^{V(G)}$ is a mapping that assigns to each node $x\in T$ its bag $\mathrm{𝖻𝖺𝗀}(x)\subseteq V(G)$ such that the following conditions are satisfied:

• $\mathrm{■}$

  For every vertex $v\in V(G)$, the set of nodes $x\in V(T)$ satisfying $v\in \mathrm{𝖻𝖺𝗀}(x)$ induces a connected subtree of $T$.

• $\mathrm{■}$

  For every edge $\{u,v\}\in E(G)$, there exists a node $x\in V(T)$ such that $u,v\in \mathrm{𝖻𝖺𝗀}(x)$.

We may assume that every internal node of $T$ has exactly two descendants. See [7] for more details on tree decompositions in general. Further, let $𝒯=(T,\mathrm{𝖻𝖺𝗀})$ be a tree decomposition of a graph $G$. The adhesion of a node $x\in V(T)$ is defined as $\mathrm{𝖺𝖽𝗁}(x)≔\mathrm{𝖻𝖺𝗀}(\mathrm{𝗉𝖺𝗋𝖾𝗇𝗍}(x))\cap \mathrm{𝖻𝖺𝗀}(x)$ and the margin of a node $x\in V(T)$ is defined as $\mathrm{𝗆𝗋𝗀}(x)≔\mathrm{𝖻𝖺𝗀}(x)\setminus \mathrm{𝖺𝖽𝗁}(x)$. The cone at a node $x\in V(T)$ is defined as $\mathrm{𝖼𝗈𝗇𝖾}(x)≔{\bigcup }_{y{⪰}_{T}x}\mathrm{𝖻𝖺𝗀}(y)$ and the component at a node $x\in V(T)$ is defined as $\mathrm{𝖼𝗈𝗆𝗉}(x)≔\mathrm{𝖼𝗈𝗇𝖾}(x)\setminus \mathrm{𝖺𝖽𝗁}(x)={\bigcup }_{y{⪰}_{T}x}\mathrm{𝗆𝗋𝗀}(y)$. Here, $y{⪰}_{T}x$ means that $y$ is a descendant of $x$ in $T$. The width of a tree decomposition is the maximum number of vertices in each bag (minus one). The treewidth of a graph $G$, noted $\text{tw}(G)$, is the minimum width among all possible tree decompositions of $G$. For directed graphs, we define these terms over their underlying undirected graphs.

We are given a DAG $G$ and two independent sets $S$ and $D$ both of size $k$. First, we can assume that $S\cup D$ is the vertex set of the entire graph, as for every other vertex $v$ no token can start in $S$, go to $v$ and then end in $D$, contradicting that $G$ is a DAG of depth 2.

If $(G,S,D)$ is a positive instance, there needs to be at least one vertex $u$ in $D$ that has just a single neighbor $v$ in $S$, as otherwise no token can move. We can therefore start the reconfiguration sequence by moving the token from $u$ to $v$. We can now remove $u,v$ from $G$ and proceed inductively in the same way. If at any point no token can move, we report that the input is a negative instance to ISR-DTS. $◀$

After this small warm up proof, let us now move to the parameterized tractability result. Let us first show, that we can assume the input to have a uniform structure.

First note, that if there is a vertex from $S-D$ at the third layer, it can reach nothing, and thus we can return a trivial no instance. While a vertex in $S\cap D$ in the third layer cannot move, blocking its in-neighborhood, so we can safely remove this vertex together with it’s in-neighborhood. By analogous arguments the same holds if there is a vertex from $D$ at the first layer. Additionally, we can remove all vertices without predecessors in $S$ (as they cannot be reached) and all vertices with no successors in $D$ (as a token here cannot reach a destination).

Observe, that after this a vertex from $S$ may not lie on the second layer. If it were so, it would have a predecessor, which then would lie in the first layer. Thus, it would be in $S$ which means that $S$ is not an independent set.

Furthermore, if a vertex $v\in D$ is in the second layer, it may not have successors. Thus, we can add a new vertex $v^{\prime }$ make it a successor to all predecessors of $v$ as well as $v$ itself. Then, while keeping $v$ in the graph, we remove $v$ from $D$ and add $v^{\prime }$ instead.

Note that all of these basic checks as well as basic graph manipulations can be carried out in polynomial time. $◀$

We show that the following reduction rule, when applied exhaustively, yields a kernel:

Let $G^{\prime }$ be the graph obtained from applying the reduction rule on $G$. Clearly if there is a reconfiguration sequence in $G^{\prime }$ one can use the same sequence in $G$. Thus, we only have to show, that if there is a reconfiguration sequence in $G$ there is one in $G^{\prime }$.

Let ${({\alpha }_i)}_{i\in I}$ be the reconfiguration. We show that every time ${({\alpha }_i)}_{i\in I}$ places a token on $u$ we can place it on $v$ instead. As $u$ and $v$ have the same neighborhood, the independent set condition is not violated and neither is the requirement of moving tokens only along edges. That is, if there is no token at $v$ at that same step. However, a token on $v$, blocking all of $N(u)$, would prohibit the placement of a token on $u$. $◀$

We first use Lemma 3.2 to obtain an instance, where the first layer is equal to $S$ and the third layer to $D$. Then we apply ˜3.3. Note, that now every vertex on the second layer has a distinct neighborhood which is a subset of $S\cup D$. As there are at most $2^{|S\cup D|}$ unique subsets, the total number of vertices is bound by $|S|+|D|+2^{|S\cup D|}=2k+4^k$. $◀$

Together Lemma 3.4 and Lemma 3.1 complete the proof of Theorem 1.1.

Let $\sigma$ be a satisfying assignment of $\phi$. We define the following reconfiguration sequence. In no particular order move a token from $x_s$ to $x_p$ if $\sigma (x)=$ True, to ${\overline{x}}_p$ otherwise.

For all literals where it is possible without violating the independent set condition, slide along $(\mathrm{\ell },{\mathrm{\ell }}^{\prime })$. I.e. this move is possible for every literal of the form $x$ (resp. $\overline{x}$) where $\sigma$ sets $x$ to True (resp. to False).

As each clause $c$ has at least one literal $\mathrm{\ell }$ that evaluates to true. Move the token from $c_s$ to $c_t$ over $c_{\mathrm{\ell }}$. This move is possible as the token in the “literal gadget” moved from $\mathrm{\ell }$ to ${\mathrm{\ell }}^{\prime }$. Now one is able to move the token from $w$ to $w^{\prime }$. Next, move the tokens on all $x_p$ or ${\overline{x}}_p$ to $x_t$ and finally from all remaining $\mathrm{\ell }$ to ${\mathrm{\ell }}^{\prime }$. $◀$

We first show, that the flow of token is tightly controlled.

By reachability in $G_{\phi }$ the only possibility where this is not the case would be if some token coming from $x_s$ ends up in ${\mathrm{\ell }}^{\prime }$ (for $x=\mathrm{\ell }$). Implying the token from $\mathrm{\ell }$ ends up in $c_t$; implying that the token from $c_s$ ends up in $w^{\prime }$; implying that the token from $w$ slides to $x_t$. However, as $w$ blocks $w^{\prime }$, $c_s$ blocks $c_{\mathrm{\ell }}$, $\mathrm{\ell }$ blocks ${\mathrm{\ell }}^{\prime }$ and $x_t$ locks in $x_s$, so none of these moves is doable. $\mathrm{⊲}$

Let ${({\alpha }_i)}_{i\in I}$ be a reconfiguration sequence certifying that $(G_{\phi },S_{\phi },D_{\phi })$ is a positive-instance. The previous claim implies that the token in $w$ ends up in $w^{\prime }$, so let ${\alpha }_i$ be the first configuration where a token occupies $w^{\prime }$. We define the following set $X^{\prime }=\{{\mathrm{\ell }}^{\prime }\in {\alpha }_i(T)\mid \mathrm{\ell }\text{ is literal}\}$.

By ˜4.3, for all clauses $c$ the token coming from $c_s$ is either at some $c_{\mathrm{\ell }}\in \{c_{{\mathrm{\ell }}_1}$, $c_{{\mathrm{\ell }}_2},c_{{\mathrm{\ell }}_3}\}$ or is already on $c_t$ and has previously been in one of the $c_{\mathrm{\ell }}$. Thus, no token can be at its neighbor $\mathrm{\ell }$ (on the literal gadget). By ˜4.3 there is now a token on ${\mathrm{\ell }}^{\prime }$.

For the second claim, assume towards a contradiction, that in ${\alpha }_i$ tokens are placed at both $\mathrm{\ell }$ and $\overline{\mathrm{\ell }}$ for some literal $\mathrm{\ell }$. This implies that neither for ${\alpha }_i$ nor for any succeeding configuration a token is at $x_p$ or ${\overline{x}}_p$ where $x$ is the variable of the literal $\mathrm{\ell }$. As no token is on $x_t$ there is one at $x_s$ and by ˜4.3 it cannot reach a valid end position. $\mathrm{⊲}$

We find the following assignment $\sigma ()$. Set $\sigma (x)=$ True, if $x\in X^{\prime }$ and otherwise $\sigma (x)=$ False. Observe, that all literals in $X^{\prime }$ evaluate to true. As $X^{\prime }$ contains at least one literal per clause all clauses evaluate to true. $◀$

This concludes the proof of Theorem 1.2.

First observe that with the absence of neighboring black holes, each step introduces a change for a planet (losing or receiving a token). As, a planet only witness $2k\iota$ many changes, this bounds the length of every sequence by $2k\iota n$, where $n=|V(G)|$.

As there are $n^k$ possible configurations, the total number of possible reconfiguration sequences of iteration $\iota$ is at most ${(n^k)}^{2k\iota n}=n^{2k^2\iota n}$. $◀$

We then call the $\iota$-profile of $x$ the set of reconfiguration $\alpha$ of iteration $\iota$ over $\mathrm{𝗐𝖺𝗋𝗉}(x)$ such that there is a reconfiguration $\beta$ over $\mathrm{𝗌𝗂𝗀𝗇𝗂𝖿𝗂𝖼𝖺𝗇𝗍}(x)$ that collapses to $\alpha$ over $\mathrm{𝗐𝖺𝗋𝗉}(x)$.

Which in turn yields the proof for Theorem 1.5.