Token Sliding Independent Set Reconfiguration on Block Graphs¹¹1A major part of the work that led to the results in this manuscript was done when both authors were affiliated with the Indian Statistical Institute, Chennai Centre

A “block” of a graph $G$ is defined to be a maximal connected subgraph $H$ of $G$ such that $H$ is a graph without any cut-vertices. (Note that it follows from this definition that if an edge $e$ of $G$ is not contained in any cycle of $G$, then $e$ together with its endpoints forms a block of $G$.) A block graph is an undirected graph in which each block is a clique. A simple way to visualize the structure of these graphs is through the following equivalent definition: every complete graph is a block graph, and every graph that is obtained by taking the disjoint union of a block graph $G$ and a complete graph $G^{\prime }$ and then identifying (i.e. merging) a vertex in $G$ with a vertex in $G^{\prime }$ is also block graph. Please refer Figure 3(a) for an example of a block graph and Section 2.2 for a formal definition of this graph class. Note that block graphs form a subclass of chordal graphs and a superclass of trees.

We prove that TS-Ind-set reconfig is polynomial-time solvable on block graphs. It is worth noting that our algorithm is the first generalization of the polynomial time algorithm of Demaine et al. for trees, since none of the other classes for which polynomial time algorithms for the problem have been obtained contains the class of trees. It was claimed in [23] and [21] that the problem can be solved in polynomial time on cactus graphs and block graphs respectively, but the authors of both papers have later announced that the algorithms are incorrect [20, 19] (also see [22, 24]), and that the complexity of the problem on both classes of graphs remains unresolved.

In this paper, we present an algorithm that takes as input a block graph $G$ having $b$ blocks, along with two independent sets $C_1,C_2$ of $G$, and determines in $O(b^4)$ time whether the independent set $C_1$ can be transformed into the independent set $C_2$ using token sliding. Note that $b$ is at most $|V(G)|$ and hence this algorithm runs in time $O({|V(G)|}^4)$.

Our algorithm is a generalization of the polynomial-time algorithm for trees given in [12]. The algorithm for trees first determines which tokens are “rigid” in both input independent sets. A token in an independent set is said to be rigid if it cannot be moved from its position by any sequence of valid token movements. Determining which tokens in an independent set are rigid is not very difficult for trees – a token on a vertex $u$ is rigid if and only if every neighbour $v$ of $u$ has a neighbour $x$ other than $u$ itself that has a token that is rigid for the tree containing $x$ in the forest $T-\{v\}$. This implies that it can be determined in linear time whether a token in a given independent set is rigid. Clearly, two independent sets whose set of vertices containing rigid tokens are unequal cannot be reconfigured with each other. Even if the vertices having rigid tokens is the same for both independent sets, if the two independent sets have an unequal number of tokens in any connected component that is obtained by the removal of the vertices containing the rigid tokens and their neighbours, it can be concluded that the independent sets are not reconfigurable with each other. It is shown in [12] that these two necessary conditions are also sufficient, i.e. any two independent sets that satisfy these two conditions can be reconfigured with each other. Thus it can be determined in linear time whether two independent sets in a tree are reconfigurable with each other. Further, their proof yields an algorithm that outputs a reconfiguration sequence of length $O(n^2)$ between the two input independent sets. Note that the result above implies that any two independent sets in a tree that have the same cardinality and contain no rigid tokens are reconfigurable with each other.

Even though similar to trees at first sight, the problem on block graphs presents many difficulties that hinder the construction of a polynomial-time algorithm similar to the one in [12]. For example, unlike for trees, two independent sets in a block graph that have the same cardinality and have no rigid tokens may not be reconfigurable with each other; see Figure 12 of [12]. This hints that instead of rigidity of tokens, one should perhaps find out which tokens are “trapped” within the blocks they are in (this is similar to the notion of “confined” tokens in [23]). However, determining which tokens are trapped in their blocks turns out to be not so straightforward.

A more important difference is perhaps the fact that in a block graph, there can be situations in which to insert one additional token into a branch of the block graph, an arbitrary number of tokens may first need to be taken out of that branch – a situation that never arises for a tree. An example of this phenomenon can be demonstrated as follows. In Figure 1, a block graph with some tokens placed on the vertices of an independent set is shown.

In the figure, $2k$ of the tokens are shown as solid black circles. There might be an arbitrary number of tokens in the set $Z$ of vertices. For each $i\in \{1,2,\mathrm{\dots },k\}$, let $A_i=\{y_1,y_2\}\cup {\bigcup }_{j\in \{1,2,\mathrm{\dots },i\}}\{x_j,u_j,v_j,w_j\}$. It can be proved that in order to place a token on $y_2$, we will have to go through an intermediate independent set in which there are at most $k$ tokens in $A_k$ (which means that at least $k$ tokens that were originally in $A_k$ are outside $A_k$ at this point). This can be easily proved by induction on $k$. If $k=1$, then clearly, before reaching an independent set with a token on $y_2$, we will have to reach an independent set with a token on $v_1$, at which point there will be at most one token in $A_1$. Let us assume inductively that the statement is true for $k-1$. Suppose that through a sequence of reconfiguration steps, we place a token on $y_2$. Then we know by the inductive hypothesis that there is some intermediate independent set in which there are at most $k-1$ tokens in $A_{k-1}$. Consider the first such independent set in the sequence of reconfiguration steps. By the choice of this independent set, it is clear that there is a token on $v_k$ in this independent set, which implies that there are no tokens on any other vertex of $A_k\setminus A_{k-1}$. This means that there are at most $k$ tokens in $A_k$ in this independent set, and we are done.

Using the construction described above, one can create situations in which it does not seem straightforward to determine whether a token is “trapped” within its block. For example, in the situation shown in Figure 2, the token A can be moved out of the block in which it is in, but determining that fact does not seem to be as easy as it is for the case of trees (the reader is encouraged to try to find a sequence of token movements that can achieve this; one such strategy is shown in Figure 6 at the end). It can be seen from a careful study of our strategy, shown in Figure 6, that we are alternately “freeing up” more and more space on the “left” and “right” sides of the graph by using the space that has already been freed up on the other side. Each time, the newly created space allows us to place a token on one of the four bottom-most vertices.

We hope that the strategy described above will serve as a motivational example for understanding Algorithm 1, which is the major part of our polynomial time algorithm for TS-Ind-set reconfig on block graphs. A sketch of the algorithm is as follows. Given a block graph $G$ and a configuration of tokens occupying the vertices of an independent set $I$ of $G$, the algorithm determines for each branch of $G$ how many additional tokens (relative to the number of tokens in that branch in the starting configuration $I$) can be moved into that branch by any sequence of token movements, assuming that any number of tokens can actually be brought to enter the branch from other parts of the graph. Once these values are obtained for each branch of $G$, we can use them to determine “rigid vertices” corresponding to the independent set $I$, which are vertices on which a token can never be placed by any sequence of token movements, starting from the configuration $I$ (note that these are different from the “rigid tokens” in [12]). We then show that similar to the algorithm of Demaine et al. [12] for trees, two independent sets $I_1$ and $I_2$ in a block graph are reconfigurable between each other if and only if the set of rigid vertices for each of these independent sets is exactly the same, and in the graph obtained by the removal of the rigid vertices, each connected component contains an equal number of tokens in both $I_1$ and $I_2$.

Note that the above description of the algorithm is only intended to develop intuition; we now give the formal definitions of the concepts that were alluded to above, which will enable us to state our algorithm and prove its correctness rigorously.

Let $G$ be a graph. We define a binary relation $\to$ on the set of independent sets of $G$ which has the property that for two independent sets $I_1$ and $I_2$ of $G$, we have $I_1\to I_2$ if and only if $I_1$ can be transformed into $I_2$ using at most one token movement. Formally, for two independent sets $I_1,I_2$ of $G$, we say that “$I_1\to I_2$” if one of the following holds:

• $\mathrm{■}$

  $I_1=I_2$, or

• $\mathrm{■}$

  $\exists v_1,v_2\in V(G)$ such that $I_1\setminus I_2=\{v_1\}$, $I_2\setminus I_1=\{v_2\}$ and $v_1{v}_2\in E(G)$.

Note that the relation $\to$ is symmetric and reflexive. For independent sets $I,I^{\prime }$ of a graph $G$, we say that $I^{\prime }$ is reachable from $I$ in $G$ if there exist independent sets $I_0,I_1,\mathrm{\dots },I_k$ of $G$, where $k\ge 0$, such that $I=I_0\to I_1\to \mathrm{\cdots }\to I_k=I^{\prime }$. Clearly, the relation “is reachable from” is an equivalence relation on the set of independent sets of $G$. Also, since the relation $\to$ preserves cardinality, i.e. since $|I_1|=|I_2|$ if $I_1\to I_2$, we have that two independent sets of $G$ that are reachable from each other are of the same cardinality.

The decision problem TS-Ind-set reconfig is defined as follows.

The following observations, which are implicitly assumed in the literature about the token sliding independent set reconfiguration problem, are easy to see (see for example Observation 4.1 in [1]).

A cut-vertex of a graph $G$ is a vertex $u\in V(G)$ such that $G-\{u\}$ has more connected components than $G$. A block in a graph $G$ is a maximal subgraph of $G$ which is isomorphic to a connected graph without any cut-vertices. For the sake of brevity of notation, we consider a block as just the set of vertices that make up the block. Thus, for us, a block of a graph $G$ is a maximal set $S\subseteq V(G)$ such that $G[S]$ is a connected graph that does not have any cut-vertices. A block graph is a graph in which each block is a clique. The following folklore observation can be easily seen to follow from the definition of a block graph.

By Observation 1, it is enough to solve the TS-Ind-set reconfig problem on connected graphs. Let $G$ be a connected block graph. Note that every vertex of $G$ is contained in some block of $G$. The vertices of $G$ that are contained in more than one block are exactly the cut-vertices of $G$. Every pair of adjacent vertices in $G$ belongs to a unique block of $G$. We denote by $V_{cut}(G)$ the set of cut-vertices of $G$ and by $ℬ(G)$ the set of blocks of $G$. It is easy to see that if $u\in V(G)\setminus V_{cut}(G)$, then there is a unique block in $ℬ(G)$ that contains $u$. For any $u\in V(G)$, we denote by ${ℬ}_u(G)$ the set of all blocks in $ℬ(G)$ that contain $u$. For any $B\in ℬ(G)$, we define $K_B(G)=B\cap V_{cut}(G)$, i.e. $K_B(G)$ is the set of cut-vertices of $G$ that also belong to $B$.

A block graph is commonly represented by its block-tree which is a tree having vertex set $V_{cut}(G)\cup ℬ(G)$ and edge set $\{uB:u\in V_{cut}(G),B\in {ℬ}_u(G)\}$ (see Figure 3). It is folklore that this definition indeed gives a tree (see for example Section 3.1 of [13]).

For a connected block graph $G$, let $𝒯(G)$ denote its block-tree with each undirected edge replaced with a pair of directed edges, one pointing in each direction. Thus $E(𝒯(G))=\{(u,B),(B,u):u\in V_{cut}(G),B\in {ℬ}_u(G)\}$. For ease of notation we let ${𝒫}_G=E(𝒯(G))$. For each $p\in {𝒫}_G$, we now define an induced subgraph $G[p]$ of $G$ as follows.

For $u\in V_{cut}(G)$ and $B\in {ℬ}_u(G)$, we define $G[(u,B)]$ (respectively $G[(B,u)]$) as the connected component containing $u$ in the graph $G-\{uv\in E(G):v\in B\}$ (resp. $G-\{uv\in E(G):v\notin B\}$). Clearly, $G[(u,B)]$ and $G[(B,u)]$ are connected graphs. By Observation 3, we have that $G[(u,B)]$ and $G[(B,u)]$ are both block graphs. Most of the time, we abbreviate $G[(u,B)]$ and $G[(B,u)]$ to just $G[u,B]$ and $G[B,u]$ respectively (see Figure 4 for a schematic diagram of an example block graph $G$ and two induced graphs $G[u,B]$ and $G[B,u]$ of it). We also abbreviate ${ℬ}_u(G[u,B])$ and $K_B(G[B,u])$ to ${\beta }_G(u,B)$ and ${\kappa }_G(B,u)$ respectively. We omit the subscript $G$ when the graph being considered is clear from the context.

We shall sometimes write just $𝒫$ instead of ${𝒫}_G$, when the graph $G$ is clear from the context. Let $G$ be a connected block graph, $u\in V_{cut}(G)$, $B\in {ℬ}_u(G)$ and $p\in \{(u,B),(B,u)\}$. We say that $u$ “is the base of $p$”. Further, if $p=(u,B)$, then we let $\overline{p}=(B,u)$ and if $p=(B,u)$, then we let $\overline{p}=(u,B)$.

For $p\in {𝒫}_G$, a set $C\subseteq V(G[p])$ that is an independent set of $G$ is called a $p$-independent set of $G$. Further, we define $\overline{C}=C\setminus \{u\}$, where $u$ is the base of $p$. For an independent set $S$ of $G$, we let $S[p]$ denote $V(G[p])\cap S$. Notice that for an independent set $S$ of $G$, the set $S[p]$ is a $p$-independent set of $G$. Depending on the context, we shall sometimes consider a $p$-independent set of $G$ to be an independent set of $G$ as well. Given an independent set (or $p$-independent set) $C$ of $G$, we say that a vertex $u$ is under attack in $C$ if $N_G(u)\cap C\ne \mathrm{\varnothing }$. Note that if $u\in C$, then $u$ is not under attack in $C$.