Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules

We use a polynomial-time reduction from IntE3-SAT. Let ${\varphi }^{\prime }$ be an instance of IntE3-SAT and $X^{\prime }$ be the set of variables of ${\varphi }^{\prime }$. We will construct an instance $(G,I,J,k\text{-}\mathrm{𝖳𝖩})$ of ISR under $k\text{-}\mathrm{𝖳𝖩}$ where $k=|I|-1$ (see Figure 1 for an illustration), and then modify for any fixed $\mu \ge 1$.

For each variable $x\in X^{\prime }$, let $a_x$ denote the number of clauses of ${\varphi }^{\prime }$ in which $x$ appears as a literal. For each variable $x\in X^{\prime }$, we set up a variable gadget $Y_x$, which is defined as a cycle with $2a_x$ vertices (note that if $x$ appears only once, then $Y_x$ is a path with two vertices). The vertices in $Y_x$ are labeled with $t_x^1,f_x^1,t_x^2,f_x^2,\mathrm{\dots },t_x^{a_x},f_x^{a_x}$ in a counterclockwise order. Intuitively, $t_x^i$ and $f_x^i$ for each $i\in [a_x]$ correspond to $T$ and $F$ assignments for $x$, respectively. We refer to a vertex of $Y_x$ corresponding to $T$ (resp. $F$) assignment to $x$ as a true vertex (resp. false vertex). For each clause $C$, we set up a clause gadget $K_C$, which is defined as a complete graph with three vertices. The vertices in $K_C$ correspond to the three literals in $C$. We refer to a vertex of $K_C$ corresponding to a positive literal (resp. negative literal) of $C$ as a positive vertex (resp. negative vertex). Finally, we connect variable gadgets and clause gadgets with edges as follows: For a vertex $v$ in a clause gadget corresponding to a literal $l$ of a variable $x$ with occurrence $i\in [a_x]$, connect $v$ to $t_x^i$ if the literal is negative; otherwise, connect $v$ to $f_x^i$. Let $G$ be the obtained graph. Observe that $G$ is a graph of maximum degree $3$. Let $I$ be a set of all false vertices in variable gadgets and a negative vertex arbitrarily chosen from each clause gadget. Let $J$ be a set of all true vertices in variable gadgets and a positive vertex arbitrarily chosen from each clause gadget. Note that such $I$ and $J$ always exist as each clause has both positive and negative literals due to the definition of IntE3-SAT. Finally, we set $k=|I|-1$.

If $\mu \ge 2$, then we also add $\mu -1$ isolated vertices to $G$. Let $V^{\ast }$ be the set of all added vertices. Then let $G^{\ast }$ be an obtained graph, $I^{\ast }=I\cup V^{\ast }$, and $J^{\ast }=J\cup V^{\ast }$. We also set $k=|I^{\ast }|-\mu$. Note that $I$ is a maximum independent set of $G$ and thus any independent set with size $|I^{\ast }|=|I|+|V^{\ast }|$ of $G^{\ast }$ contains $V^{\ast }$. This allows us to move at most $k=|I^{\ast }|-\mu =|I|+|V^{\ast }|-\mu =|I|-1$ tokens simultaneously only on $G$. Therefore, $(G,I,J,(|I|-1)\text{-}\mathrm{𝖳𝖩})$ is a yes-instance if and only if $(G^{\ast },I^{\ast },J^{\ast },(|I^{\ast }|-\mu )\text{-}\mathrm{𝖳𝖩})$ is a yes-instance.

For this reason, we discuss only the case when $\mu =1$ here. The instance $(G,I,J,k\text{-}\mathrm{𝖳𝖩})$ of ISR under $k\text{-}\mathrm{𝖳𝖩}$ is clearly obtained in polynomial time. To complete our reduction, we will show that ${\varphi }^{\prime }$ is a yes-instance of IntE3-SAT if and only if $(G,I,J,k\text{-}\mathrm{𝖳𝖩})$ is a yes-instance of ISR under $k\text{-}\mathrm{𝖳𝖩}$ where $k=|I|-1$.

Assume that there is a variable assignment $b^{\prime }$ that is mixed and satisfies ${\varphi }^{\prime }$. We construct an independent set $I^{\prime }$ of $G$ as follows. For a variable $x_i$ with $i\in [n]$, if $x_i$ is assigned $T$, then all true vertices of $Y_{x_i}$ are contained in $I^{\prime }$. Similarly, if $x_i$ is assigned $F$, then all false vertices of $Y_{x_i}$ are contained in $I^{\prime }$. Since those vertices are chosen according to $b^{\prime }$, one vertex in each clause gadget that corresponds to a literal evaluating $T$ can also be contained in $I^{\prime }$. Furthermore, since $b^{\prime }$ is mixed, we have $|I\cap I^{\prime }|\ge 1$ and $|I^{\prime }\cap J|\ge 1$. Therefore, a reconfiguration sequence $\sigma =⟨I,I^{\prime },J⟩$ exists.

Conversely, assume that there is a reconfiguration sequence $\sigma =⟨I=I_0,I_1,\mathrm{\dots },I_{\mathrm{\ell }}=J⟩$. Consider an integer $i\in [\mathrm{\ell }]$ such that tokens on $I_i$ are placed on true vertices for the first time. In other words, all tokens of $I_{i-1}$ in variable gadgets are on false vertices. Since any positive vertex of any clause gadget is adjacent to a false vertex of a variable gadget, all positive vertices are not in $I_{i-1}$. Then, we claim that not all true vertices are in $I_i$. For the sake of contradiction, assume that all true vertices are in $I_i$. Then, since each negative vertex is adjacent to a true vertex, each token of $I_i$ in clause gadgets is on a positive vertex. Thus, since $I_{i-1}$ contains only false vertices and negative vertices, $I_{i-1}\cap I_i=\mathrm{\varnothing }$. However, $|I_{i-1}\cap I_i|\ge 1$ must hold because they are adjacent under $k\text{-}\mathrm{𝖳𝖩}$, which is a contradiction. Therefore, we conclude that $I_i$ contains both true and false vertices. From our construction of the variable gadgets, either true or false vertices are in $I_i$ for each variable gadget. For each $j\in [n]$, let $b^{\prime }$ be a variable assignment such that $x_j$ is assigned $T$ if and only if true vertices of $Y_{x_j}$ are in $I_i$. Then, literals of clauses in ${\varphi }^{\prime }$ corresponding to vertices in $I_i$ evaluate $T$ from our construction, that is, $b^{\prime }$ satisfies ${\varphi }^{\prime }$. Therefore, ${\varphi }^{\prime }$ is a yes-instance of IntE3-SAT. $◀$

By Theorem 2, we have proven the $\mathrm{𝖭𝖯}$-hardness of ISR under $k\text{-}\mathrm{𝖳𝖩}$ on graphs of maximum degree 3 unless we can move all tokens. We now proceed to the $\mathrm{𝖭𝖯}$-hardness of ISR under $k\text{-}\mathrm{𝖳𝖩}$ on planar graphs of maximum degree $4$. The constructed graph $G$ in the proof of Theorem 2 may have some edges crossing on a plane. We will eliminate these crossings by replacing them with a crossover gadget (as shown in Figure 2). A crossover gadget consists of eight vertices $u_1^{\prime },u_2^{\prime },v_1^{\prime },v_2^{\prime },w_1,\mathrm{\dots },w_4$ and twelve edges: $u_1^{\prime }{w}_1$, $u_1^{\prime }{w}_4$, $u_2^{\prime }{w}_2$, $u_2^{\prime }{w}_3$, $v_1^{\prime }{w}_1$, $v_1^{\prime }{w}_2$, $v_2^{\prime }{w}_3$, $v_2^{\prime }{w}_4$, $w_1{w}_2$, $w_2{w}_3$, $w_3{w}_4$, and $w_4{w}_1$. For two crossing edges $u_1{u}_2$ and $v_1{v}_2$ of $G$, replacing this crossing with a crossover gadget means removing the edges $u_1{u}_2$ and $v_1{v}_2$, inserting a crossover gadget, and adding the edges $u_1{u}_1^{\prime }$, $u_2{u}_2^{\prime }$, $v_1{v}_1^{\prime }$, and $v_2{v}_2^{\prime }$. The crossover gadget always contains exactly three tokens corresponding to a maximum independent set of the gadget.

As the same reason in the proof of Theorem 2, we provide the proof when $\mu =1$ (that is, $k=|I|-1$). Let $(G,I,J,k\text{-}\mathrm{𝖳𝖩})$ be the instance of ISR constructed from ${\varphi }^{\prime }$ in the proof of Theorem 2, where $k=|I|-1$. Consider any drawing of $G$ on the plane, which may have crossings.

To make $G$ into a planar graph of maximum degree $4$, we replace each crossing in the drawing with a crossover gadget, which is shown in Figure 2. Suppose that we replaced a crossing of edges $u_1{u}_2$ and $v_1{v}_2$ with a crossover gadget. We claim that the crossover gadget correctly “simulates” the crossing if the crossing is good, that is, every independent set $I^{\prime }$ of $G$ with size $|I|$ satisfies $|I^{\prime }\cap \{u_1,u_2\}|=|I^{\prime }\cap \{v_1,v_2\}|=1$. Although not every drawing of $G$ meets this condition¹¹1For example, the drawing in Figure 1 contains a non-good crossing of two edges $f_{x_3}^2{v}_{x_3}$ and $f_{x_4}^2{u}_{x_4}$, where the two vertices $v_{x_3}$ and $u_{x_4}$ correspond to the literal $x_3$ in clause $C_3$ and the literal $x_4$ in clause $C_2$, respectively. In this crossing, $f_{x_3}^2$ and $v_{x_3}$ are both not in the independent set $J$., we claim that $G$ always admits a drawing where all crossings are good. To this end, we construct a drawing of $G$ in which all edge crossings occur only between edges belonging to distinct variable gadgets.

Let $m$ be the number of clauses and $n$ be the number of variables in ${\varphi }^{\prime }$, respectively. We will represent all variable gadgets and clause gadgets on a grid with $(2n+3)$ rows and $6m$ columns such that edges between variable gadgets and clause gadgets have no crossing (see also Figure 3). Let $(i,j)$ be the coordinates of a point on the Euclidean plane, where $i\in [6m]$ and $j\in [2n+3]$. For each clause gadget corresponding to a clause $C_i$ of ${\varphi }^{\prime }$, the three literal vertices of the gadget are positioned at $(6(i-1)+1,2)$, $(6(i-1)+3,2)$, and $(6(i-1)+5,2)$. Furthermore, the edges are embedded to minimize the sum of their length, with one of the three edges utilizing the bottom border. If a literal vertex, corresponding to the $j$-th occurrence of a literal of variable $x$, is placed at $(i^{\prime },2)$, then the true vertex $t_x^j$ and the false vertex $f_x^j$ are positioned at $(i^{\prime },3)$ and $(i^{\prime }+1,3)$, respectively, and are connected by a shortest edge.

Additionally, each literal vertex is joined with either of them, which follows the construction of $G$ in the proof of Theorem 2: for a vertex $v$ in a clause gadget corresponding to a literal $l$ of a variable $x$ with occurrence $j\in [a_x]$, connect $v$ to $t_x^j$ if $l$ is negative, and to $f_x^j$ otherwise. Then, for a variable gadget corresponding to a variable $x_p$ with $p\in [n]$, we embed the remaining edges in the gadget using only the vertical lines where its vertices are located and the $(2p+2)$-th and $(2p+3)$-th horizontal lines, minimizing the total length. (If the variable gadget is a path with 2 vertices, there is nothing to do.)

Now, a new embedding of $G$ is obtained and denoted by $D(G)$. Although $D(G)$ and $G$ are isomorphic, $D(G)$ only has crossing edges in variable gadgets. Since every variable gadget forms a cycle of even length and has tokens placed alternately on its vertices, exactly one endpoint of each edge in the variable gadgets belongs to any independent set of $G$ of size exactly $|I|$. Thus, all crossings of $D(G)$ are good.

We pick a crossing of two edges, say $u_1{u}_2$ and $v_1{v}_2$. Since both $u_1{u}_2$ and $v_1{v}_2$ are edges of variable gadgets, we may assume without loss of generality that $u_1,v_1\in I$ and $u_2,v_2\in J$. We then replace this crossing with our crossover gadget. Let $G^{\ast }$ denote the resulting graph. For the initial (resp. target) independent set $I$ (resp. $J$) of $G$, adding three tokens on $w_1$, $u_2^{\prime }$, and $v_2^{\prime }$ (resp. $w_3$, $u_1^{\prime }$, and $v_1^{\prime }$) in the crossover gadget (as shown in Figure 4) results in the independent set $I^{\ast }$ (resp. $J^{\ast }$). Let $(G^{\ast },I^{\ast },J^{\ast },k\text{-}\mathrm{𝖳𝖩})$ be a new instance of ISR under $k\text{-}\mathrm{𝖳𝖩}$, where $k=|I^{\ast }|-1$. Note that, since the sets of vertices added to $I$ and $J$ are disjoint, we have $I^{\ast }\cap J^{\ast }=\mathrm{\varnothing }$.

For each configuration of tokens on $u_1$, $u_2$, $v_1$, and $v_2$ in $G$, there exists a unique configuration of three tokens on the crossover gadgets in $G^{\ast }$ as shown in Figure 5. Thus, the configuration of tokens on the vertices of the crossover gadget can be changed in $G^{\ast }$ if and only if the configuration of tokens on $u_1$, $u_2$, $v_1$, and $v_2$ is changed in $G$. Therefore, by faithfully simulating token moves along the edges $u_1{u}_2$ and $v_1{v}_2$ of $G$ using the token arrangements shown in Figure 5, one can show that $(G,I,J,k\text{-}\mathrm{𝖳𝖩})$ is a yes-instance if and only if $(G^{\ast },I^{\ast },J^{\ast },k\text{-}\mathrm{𝖳𝖩})$ is a yes-instance.

The graph $G^{\ast }$ has one less edge crossing than $G$. Consequently, we can obtain a plane graph $G^{\prime }$ by repeating the above replacement for each crossing of $D(G)$. As $D(G)$ has $O(mn)$ crossings, the construction of $G^{\prime }$ can be done in polynomial time. Since a crossover gadget is a graph of maximum degree $4$, $G^{\prime }$ is a plane graph of maximum degree $4$. This completes our proof. $◀$

When $\mu =0$, there exists a reconfiguration sequence $⟨I,J⟩$ of length $1$. Therefore, we assume that $\mu \ge 1$. Consider any shortest reconfiguration sequence $\sigma =⟨I=I_0,I_1,\mathrm{\dots },I_{\mathrm{\ell }}=J⟩$ between $I$ and $J$. Let $ℐ=\{I_i:i\in \{0,1,\mathrm{\dots },\mathrm{\ell }\},i\text{ is even}\}$. Note that $|ℐ|=\lfloor \frac{\mathrm{\ell }}{2}\rfloor +1$. Since $\sigma$ is the shortest reconfiguration sequence, for any two independent sets $I_i$ and $I_j$ in $ℐ$ with , we have ; otherwise, $I_i$ and $I_j$ are adjacent under $k\text{-}\mathrm{𝖳𝖩}$ and we can obtain a shorter reconfiguration sequence ${\sigma }^{\prime }$ from $\sigma$ by removing all independent sets $I_{i+1},\mathrm{\dots },I_{j-1}$, which is a contradiction. Then, we observe that $ℐ$ is an $(n,|I|,\{0,\mathrm{\dots },\mu -1\})$-system. By using Equation 2, we have

Therefore, the length $\mathrm{\ell }$ of $\sigma$ is at most $O({(\frac{n}{|I|-\mu })}^{\mu })=O({(\frac{n}{k})}^{\mu })$. $◀$

Now, we can prove Theorem 4.

It is trivial when $\mu =0$, thus we assume that $\mu \ge 1$. Suppose first that $2\mu \ge |I|$. Then, there is some constant $c$ such that since $\mu =O(\log |I|)$. We can solve ISR under $k\text{-}\mathrm{𝖳𝖩}$ by enumerating all independent sets of $G$ with constant size in polynomial time.

Suppose next that for sufficiently large $|I|$. Let $A$ and $B$ be two independent sets such that $A\subseteq I$ and $B\subseteq J$ with size exactly $\mu$. Let $G^{\ast }$ be the subgraph of $G$ obtained by removing all vertices in $N[A\cup B]$. If $G^{\ast }$ has an independent set $I^{\ast }$ with size $k$, then there is a reconfiguration sequence $⟨I,A\cup I^{\ast },B\cup I^{\ast },J⟩$ between $I$ and $J$. We say that this reconfiguration sequence is a simple reconfiguration sequence. Since the vertex set of $G^{\ast }$ is $V(G)\setminus N[A\cup B]$, the size of $V(G^{\ast })$ is at least $n-2\mu (\mathrm{\Delta }+1)$, where $\mathrm{\Delta }$ is the maximum degree of $G$. Let $\chi$ and ${\chi }^{\ast }$ be the chromatic numbers of $G$ and $G^{\ast }$, respectively. Then, we observe that ${\chi }^{\ast }\le \chi$. By the relationship between the chromatic number and the independence number, $G^{\ast }$ has an independent set with size at least $|V(G^{\ast })|/{\chi }^{\ast }\ge (n-2\mu (\mathrm{\Delta }+1))/{\chi }^{\ast }$. Thus, if $(n-2\mu (\mathrm{\Delta }+1))/{\chi }^{\ast }\ge k$, then $I$ and $J$ are always reconfigurable, as a simple reconfiguration sequence exists. Note that the length of a simple reconfiguration sequence is $3$.

It remains to consider the case where , in which a simple reconfiguration sequence between $I$ and $J$ may not exist. Combined with Lemma 5, the length $\mathrm{\ell }$ of a shortest reconfiguration sequence between $I$ and $J$ satisfies

Since $\mu =O(\log |I|)=O(\log n)$ and $\mathrm{\Delta }=o(\frac{n}{\log n})$, we have $\mu \mathrm{\Delta }=o(n)$. Hence, we have $(2\mu (\mathrm{\Delta }+1))/n=o(1)$. Furthermore, ${\chi }^{\ast }\le \chi =O(1)$. Thus, from Equation 3, we have