The Tape Reconfiguration Problem and Its Consequences for Dominating Set Reconfiguration

The main focus of this paper is to study the parameterized complexity of reconfiguration problems restricted to sparse classes of graphs and in particular the case of Dominating Set Reconfiguration, or DSR for short. There are three different natural adjacency relations one can consider between dominating sets, which gave rise to three different models in the literature; namely the token jumping (TJ) model, the token sliding (TS) model, and the token addition/removal (TAR) model. Since the TAR model is known to be polynomially equivalent to the TJ model [13], we only discuss the other two.

In the token jumping model, we say that two solutions $S,S^{\prime }$ are adjacent if both $S\setminus S^{\prime }$ and $S^{\prime }\setminus S$ have size at most one. In other words, we can remove a vertex of $S$ and add a vertex of $S^{\prime }$ to transform $S$ into $S^{\prime }$. In the token view of the problem, we say a token jumps from some vertex $u$ to another (possibly already occupied) vertex $v$. In the token sliding model, we additionally require that $uv\in E$, i.e., the vertices $u$ and $v$ must be adjacent, and the token is said to slide on the edge $uv$ from $u$ to $v$. We shall use TS-$\mathrm{\Pi }$ and TJ-$\mathrm{\Pi }$ to denote the reconfiguration variant of problem $\mathrm{\Pi }$ under the token sliding and token jumping model, respectively. For instance, TS-DSR corresponds to DSR in the token sliding model and TJ-DSR corresponds to DSR in the jumping model.

TJ-DSR is known to be PSPACE-complete on split graphs, bipartite graphs [13, 27, 32], and planar graphs of maximum degree $3$ [29] and bounded-bandwidth graphs [42]¹¹1Bandwidth is a very restricted subclass of pathwidth which, in turn, is a restriction of treewidth. That is bandwidth$(G)\ge$ pathwidth$(G)\ge$ treewidth$(G)$.. On the positive side, linear-time algorithms are known for trees, interval graphs, and cographs. As for TS-DSR, the problem is known to be PSPACE-complete on circle graphs [16], split graphs [13], bipartite graphs [13], and planar bounded-bandwidth graphs of maximum degree three [42]. Polynomial-time algorithms for TS-DSR are known for circular-arc graphs, dually chordal graphs, and cographs [28, 13, 16, 4].

Even though both TS-DSR and TJ-DSR are known to be PSPACE-complete restricted to instances of constant bandwidth/pathwidth/treewidth, an exact constant above which the problems become hard is not explicit in the hardness proofs of Wrochna [42]. Determining an explicit upper bound for which the problems are hard has been left open for almost a decade now, see e.g. [8, 16, 5].²²2The question is open for a wealth of reconfiguration problems including Independent Set Reconfiguration, Vertex Cover Reconfiguration, Shortest Path Reconfiguration, and Dominating Set Reconfiguration. Our first main result consists in giving an explicit upper bound on the treewidth and even the pathwidth above which the TS-DSR problem becomes PSPACE-complete. Our proof uses a completely different approach from the one of Wrochna [42] and is based on a new problem, namely Tape Reconfiguration (Tape-Rec), we introduce and prove to also be hard (formal definitions in Section 2.1).

The existence of explicit constants $b$ and $w$ for which (i) TS-DSR is PSPACE-complete in graphs of bandwidth $b$, and (ii) TJ-DSR is PSPACE-complete in graphs of pathwidth or treewidth at most $w$ is also open. Unfortunately, our proof technique does not yield such explicit constants. Moreover, it is very unlikely that a small variation of our proof technique can provide such constants since this would almost automatically imply that the problems (parameterized by dominating set size $k$) are also XL-complete when restricted to the aforementioned graph classes, which is in contradiction with known results [18]. This follows, in part, from the fact that our reductions construct instances in which the dominating set size is negligible with respect to $n$.

We note that the constants $12$ and $18$ are probably not optimal. In particular, the complexity status of both TJ-DSR and TS-DSR in outerplanar graphs (which are graphs of treewidth at most $2$) is still open. We will discuss in more detail the proof technique in Section 3, but note that the proof technique of Theorem 1 is drastically different from the one of Wrochna [42] since the size of the dominating set is linear in the size of the graph in [42] while it is independent from $n=|V(G)|$ in our proof. This, in turn, allows us to derive the non-existence of parameterized algorithms which was completely out of reach with the techniques of [42].

A systematic study of the parameterized complexity of reconfiguration problems was initiated by Mouawad et al. [38]. This was followed by a long sequence of results trying to push the tractability boundary of many reconfiguration problems (see [18] for a survey which mainly focuses on dominating set and independent set reconfiguration results).

On general graphs, TJ-DSR and TS-DSR are W[2]-complete parameterized by the dominating sets size $k$ plus the length of a reconfiguration sequence $\mathrm{\ell }$ [38, 10]. For the parameter $k$ alone, it was shown by Bodlaender et al. [10] that both problems are XL-complete³³3XL is a complexity class that contains the W-hierarchy and which naturally contains most of the reconfiguration problems. In particular, when a problem is XL-complete it is very unlikely that it is FPT. if $\mathrm{\ell }$ is not given, XNL-complete if $\mathrm{\ell }$ is given in binary, and XNLP-complete if $\mathrm{\ell }$ is given in unary as part of the input. The constructions of Bodlaender et al. [10] result in heavily dense graphs that contain all possible subgraphs $H$ as subgraphs. In particular, it was left as an open problem whether the token sliding and token jumping variants of the problems behave the same on $H$-free graphs⁴⁴4A graph $G$ is $H$-free if it does not contain $H$ as an induced subgraph. That is, there is no subset of vertices in $G$ whose induced subgraph is isomorphic to $H$. A graph $G$ is $H$-minor-free if it does not contain $H$ as a minor. That is, $H$ cannot be formed from $G$ by deleting vertices and edges and by contracting edges..

When parameterized by $\mathrm{\ell }$ alone, both TJ-DSR and TS-DSR are FPT on any class of graphs where first-order model-checking is FPT, e.g., nowhere dense classes [26] and classes of bounded twinwidth [14] (assuming a contraction sequence is given as part of the input). Indeed, for the parameter $\mathrm{\ell }$, we can find a fixed sentence expressing the existence of a reconfiguration sequence of length $\mathrm{\ell }$.

Unfortunately, the approach via first-order model-checking does not help us deal with the parameterization by $k$ since reconfiguration sequences might be arbitrarily long compared to $k$. It is not possible to state the existence of such a sequence in first-order logic with a bounded length sentence. Instead, the key tool to tackle TJ-DSR parameterized by $k$ alone is based on the notion of domination cores [20]. In fact, the complexity of TJ-DSR parameterized by $k$ is quite well understood for sparse classes of graphs. The problem is known to be FPT parameterized by $k$ for biclique-free graphs and semi-ladder-free graphs [35, 24] (classes encompassing nowhere dense and degenerate graphs). In particular, it restricts quite a lot the type of graph on which TJ-DSR might be XL-complete.

On the other hand, the parameterized complexity of TS-DSR remains open even when restricted to very simple graph classes such as bounded pathwidth or treewidth graphs⁵⁵5Note that the parameterized complexity status of TS-DSR on bounded bandwidth graphs is trivially FPT since the number of vertices is upper bounded by a function of the bandwidth and the domination number. or planar graphs. This difference of knowledge between the sliding and jumping variants is also observed for other problems such as Independent Set Reconfiguration (ISR) where the token jumping version is known to be FPT (parameterized by $k$) on $K_{\mathrm{\ell },\mathrm{\ell }}$-free graphs while its sliding counterpart is only known to be FPT on planar graphs and is open beyond [18]. Bodlaender et al. [10] mentioned that “it would be interesting to investigate for which graph classes switching between token jumping and token sliding does affect the parameterized complexities”. The second goal of this paper is to study this question via the lens of Dominating Set Reconfiguration.

In the token sliding case, apart from the few polynomial results on very restricted classes, no FPT algorithm parameterized by $k$ is known. The existence of such an algorithm is conjectured in several papers including [18, 36, 8] or the recent survey [18]. The second main contribution of this article makes a step towards closing this gap by proving the following theorem:

A feedback vertex is a subset of vertices whose deletion leaves an acyclic graph. The feedback vertex set number is the minimum size of a feedback vertex set. The first hardness result of Theorem 2 (for pathwidth and treewidth) is again a consequence of the hardness of the Tape-Rec problem. The second hardness result is also based on the hardness of Tape-Rec but the proof is more technical since we need to maintain a small feedback vertex set number. One can wonder if we can strengthen the result of Theorem 2 by replacing feedback vertex set number by vertex cover number. The answer is negative. A vertex cover is a subset of vertices whose deletion leaves an independent set. Recall that given a simple undirected graph $G$, a set of vertices $I\subseteq V$ is an independent set if the vertices of $I$ are pairwise non-adjacent. The vertex cover number is the minimum size of a vertex cover. We note that TS-DSR parameterized by $k$ plus the vertex cover number is trivially FPT. This follows from the fact that given a vertex cover $C$, we can partition $R=V\setminus C$ into classes such that two vertices belong to the same class if and only if they have the same neighbors in $C$. All classes consist of independent sets (since $C$ is a vertex cover) and any class containing more than $k$ vertices can be reduced since no more than $k$ vertices can be used from a class (and all vertices of a class are “equivalent”). Hence, we obtain an instance with at most $|C|+2^{|C|}k$ vertices (assuming no isolated vertices).

Theorem 2 answers, as mentioned before, a problem that has been left open in several previous articles [18, 36, 8, 18]. The result ensures that, even in very restricted sparse graph classes, TS-DSR and TJ-DSR behave completely differently. To our knowledge, it is the first time the token sliding and token jumping models behave differently for a reconfiguration problem on a class of bounded treewidth (and even nowhere dense)⁶⁶6For sparse graphs, such a difference has already been observed for bounded degeneracy graphs for instance [18]. Actually, it is, as far as we know, the first reconfiguration problem that is not FPT on bounded treewidth graphs. It also ensures that TS-DSR and TS-ISR behave very differently on nowhere dense classes of graphs (since an easy applications of the lemmas of [8] ensures that TS-DSR is FPT parameterized by $k$ plus the feedback vertex set number). Moreover, our results provide the first (and infinite) collection of graphs (any supergraph of a large enough biclique) for which TS-DSR is XL-complete parameterized by $k$ while TJ-DSR is FPT, which partially answers the question of [10].

To sum up, our results make progress in three directions by showing that:

1. 1.

   TS and TJ do not necessarily behave the same on graphs of bounded treewidth (and below);

2. 2.

   ISR and DSR do not behave the same on nowhere dense graph classes; and

3. 3.

   TJ-DSR and TS-DSR behave differently on infinitely many $H$-free graphs.

We complement our negative results by positive results proving that TS-DSR is FPT on planar graphs (and actually beyond), answering a problem left open in [18].

To obtain the positive result, we adapt the strategy used in the token jumping model via domination cores to handle the case where the size of a forbidden minor is not too large (namely $K_{4,\mathrm{\ell }}$-minor-free graphs). However, while the proof is almost direct in the token jumping variant whenever domination cores exist, the proof gets more technical here as connectivity matters. Note that this method cannot be generalized much further since we prove that TS-DSR is XL-complete for graphs of treewidth at most $12$, and when parameterized by $k$ plus feedback vertex set number. However, it would be interesting to understand the limit between tractability and intractability on $H$-minor free graphs.

Our proof techniques are actually strong enough to be generalized further to the Connected Dominating Set Reconfiguration problem (CDSR). Recall that a dominating set $D$ is a connected dominating set if the graph induced by $D$ is connected. Deciding whether a given graph contains a connected dominating set of size at most $k$ is known to be NP-complete [33] and W[2]-complete parameterized by $k$ [21].

TS-CDSR and TJ-CDSR, the corresponding reconfiguration variants, are known to be PSPACE-complete (even on graphs of bounded pathwidth) and W[1]-hard parameterized by $k+\mathrm{\ell }$ [36, 10]. Moreover, TJ-CDSR parameterized by $k+\mathrm{\ell }$ remains W[1]-hard even when restricted to $5$-degenerate graphs. On the positive side, TJ-CDSR parameterized by $k$ is known to be FPT on planar graphs [36].

TJ-CDSR parameterized by $k$ has been conjectured to be FPT on every nowhere dense class of graphs in several papers, see e.g. [18, 36]. In [36], the authors ask whether TJ-CDSR and TS-CDSR parameterized by $k$ are FPT on graphs of bounded pathwidth. We provide a negative answer to all of the aforementioned questions. Our proof techniques can also be adapted for other dominating set variants such as distance $d$ dominating sets and total dominating sets which have been studied in the literature.

Deciding whether a given graph contains an independent set of size at least $k$ is known to be NP-complete [33] and W[1]-complete parameterized by (solution size) $k$ [21].

The Independent Set Reconfiguration (ISR) problem is another central problem that has been very widely studied under the combinatorial reconfiguration framework. Both TJ-ISR and TS-ISR are known to be PSPACE-complete restricted to planar graphs of bounded bandwidth [42, 41] and XL-complete when parameterized by the size of independent sets $k$ [10].

Similarly to TJ-DSR, the complexity of the token jumping variant, i.e., TJ-ISR, is rather well understood. Indeed, Ito et al. [31] proved that TJ-ISR parameterized by $k$ is FPT on planar graphs. This result has been generalized to nowhere dense and degenerate classes in [35, 1] and even to $K_{d,d}$-free graphs in [17]. The idea of these proofs is to follow a two-step strategy. First, an “important” subset $X$ of vertices of bounded size is identified. Second, the remaining vertices are classified according to their neighborhood in $X$, and it is shown that if some class is too large then it can be reduced.

Again, the situation becomes a lot less clear when we consider the token sliding model, i.e., TS-ISR. For instance, while TJ-ISR is trivial on chordal graphs [32], TS-ISR is PSPACE-complete on split graphs [9]. Lokshtanov and Mouawad [34] showed that, in bipartite graphs, TJ-ISR is NP-complete while TS-ISR remains PSPACE-complete.

Just like DSR, even after a decade of research, very little is known about the parameterized complexity of ISR under the token sliding model. It was proved in [6] that TS-ISR is FPT on bipartite $C_4$-free graphs. The result was later generalized by Bartier et al. [8] on planar graphs and graphs of bounded maximum degree and graphs of girth at least $5$ [7]. One can easily use the reduction rules introduced in [8] in order to prove that TS-ISR is FPT parameterized by $k$ plus the feedback vertex set number of the graph, which shows that the behavior of TS-DSR and TS-ISR is very different on sparse graph classes.