Polynomial-time solvability

indepen-dent set I_sol of G anoutput solutionto (G, l, I₀). Note that a given independent set I₀ may itself be an output solution. Opt-ISRsimply outputs a solution to (G, l, I₀), and does not require the specification of an actual reconfiguration sequence from I0

to the output solution.

We close this section with noting the following observation which says that Opt-ISR for an instance (G,0, I0) is equivalent to finding a maximum independent set of G.

Lemma 5.1 Every maximum independent set I_max of a graph Gis a solution to an instance (G,0, I0) of Opt-ISR, where I0 is any independent set of G.

5.2 Polynomial-time solvability

In this section, we study the polynomial-time solvability ofOpt-ISR.

5.2.1 Hardness results

Lemma 5.1 implies that results for the maximum independent set problem can be applied to Opt-ISR for l= 0. For example, we have the following theorem, because maximum independent set remains NP-hard for planar graphs [14].

Theorem 5.1 Opt-ISR is NP-hard for planar graphs andl= 0, wherel is a lower bound on the size of independent sets.

It is known that the degeneracy of any planar graph is at most five [23], and hence we have the following corollary.

Corollary 5.1 Opt-ISR is NP-hard for 5-degenerate graphs and l = 0, where l is a lower bound on the size of independent sets.

104 Chapter 5 Optimization variant

(a) G , I

′ r′

u

(b) G

Figure 5.1: (a) Graph G^′ and its independent set I_r^′ for MISR, and (b) the cor-responding graph G for Opt-ISR, where newly added edges are depicted by thick dotted lines.

This corollary implies thatOpt-ISR admits neither a fixed-parameter algorithm nor an XP algorithm when parameterized by d+l under the assumption that P̸= NP, wheredis the degeneracy of an input graph andl is a lower bound on the size of independent sets. We will discuss the fixed parameter (in)tractability ofOpt-ISR more deeply in Section 5.3.

We then show that Opt-ISR is PSPACE-hard even if the pathwidth of an input graph is bounded by a constant. The following theorem is the main result of this subsection.

Theorem 5.2 Opt-ISR is PSPACE-hard for bounded pathwidth graphs.

Proof. We give a polynomial-time reduction from the reachability variant of maxi-mum independent set reconfigurationproblem (MISRfor short), defined as follows [35]: We are given a graphG^′, and two maximum independent sets I₀^′ andI_r^′ ofG^′, and asked to determine whether or notI₀^′ ↭^l′ I_r^′, wherel^′ =|I₀^′| −1 = |I_r^′| −1.

We denote by a triple (G^′, I₀^′, I_r^′) an instance of MISR. This problem is known to be PSPACE-complete for bounded bandwidth graphs [35]. Since the pathwidth of a graph is at most the bandwidth of the graph [31], MISR is PSPACE-complete also for bounded pathwidth graphs.

Let (G^′, I₀^′, I_r^′) be an instance ofMISR such that the pathwidth ofG^′ is bounded by a constant. Then, we construct a corresponding instance (G, l, I₀) ofOpt-ISR, as

5.2 Polynomial-time solvability 105 follows. (See also Figure 5.1.) We add a new vertexuto the graphG^′, and join it with all vertices in V(G^′)\I_r^′; let G be the resulting graph, that is,V(G) =V(G^′)∪ {u} and E(G) = E(G^′)∪ {uv : v ∈ V(G^′)\I_r^′}. Since the pathwidth of G^′ is bounded by a constant and V(G) = V(G^′)∪ {u}, the pathwidth of G is also bounded by a constant. Let l =|I₀^′| −1 = |I_r^′| −1, and I₀ = I₀^′. This completes the construction of the corresponding instance (G, l, I₀) ofOpt-ISR. This construction can be done in polynomial time.

We now prove the correctness of our reduction. We first claim that G has only one maximum independent set, and it is I_r^′ ∪ {u}of size |I_r^′|+ 1. To see this, recall that I_r^′ is a maximum independent set of G^′. Therefore, if G has an independent set I such that |I| > |I_r^′|, it must contain u. Since u is adjacent to all vertices in V(G^′)\I_r^′, only I_r^′ ∪ {u} can be such an independent set of size|I_r^′|+ 1, as claimed.

Therefore, to complete the correctness proof of our reduction, we prove that Opt-ISR for (G, l, I₀) outputs I_r^′ ∪ {u} if and only if I₀^′ ↭^l I_r^′ on G^′. Since I_r^′ ∪ {u} is the unique maximum independent set inG, we indeed prove that I₀ ↭^l I_r^′∪ {u} on G if and only if I₀^′ ↭^l I_r^′ onG^′.

We first prove the if direction. Suppose that I₀^′ ↭^l I_r^′ on G^′. Since G contains G^′ as an induced subgraph, we have I0 = I₀^′ ↭^l I_r^′ on G. Then, I_r^′ ∪ {u} can be obtained simply by adding u toI_r^′, and hence we can conclude that I₀ ↭^l I_r^′ ∪ {u} on G.

We next prove the only-if direction. Suppose that I0

↭l I_r^′ ∪ {u} on G, that is, there exists a reconfiguration sequence I = ⟨I₀, I₁, . . . , I_ℓ = I_r^′ ∪ {u}⟩ on G under the TARl rule. Let I_q+1 be the first independent set in I which contains u; notice that I_q = I_q+1 \ {u} because we know u ̸∈ I₀. Since I_q+1 is an independent set of G, no vertex in I_q =I_q+1\ {u} is adjacent to u. By the construction of u, we thus have I_q ⊆I_r^′. Since I_q appears in I, we know |I_q| ≥ l. Therefore, we can construct a reconfiguration sequence Iqr between I_q and I_r^′ under the TARl rule by simply

106 Chapter 5 Optimization variant adding the vertices inI_r^′ \I_q one by one. Then, by combining ⟨I₀, I₁, . . . , I_q−1⟩ and Iqr serially, we can obtain a reconfiguration sequence between I₀ and I_r^′ under the TARl rule such that all independent sets in the sequence do not containu. We thus

haveI₀^′ ↭^l I_r^′ on G^′. 2

5.2.2 Linear-time algorithm for chordal graphs

A graph G ischordal if every induced cycle in G is of length three [8]. The main result of this subsection is the following theorem.

Theorem 5.3 Opt-ISR is solvable in linear time for chordal graphs.

This theorem can be obtained from the following lemma; we note that a maximum independent set I_max of a chordal graph can be found in linear time [13], and the maximality of a given independent set can be checked in linear time.

Lemma 5.2 Let (G, l, I₀) be an instance of Opt-ISR such that G is a chordal graph, and let I_max be any maximum independent set of G. Then, a solution I_sol to (G, l, I₀) can be obtained as follows:

I_sol = {

I₀ if I₀ is a maximal independent set of G and |I₀|=l;

I_max otherwise.

Proof. We first consider the case where I₀ is a maximal independent set of G and |I₀| = l. In this case, we cannot remove any vertex from I₀ because |I₀| = l.

Furthermore, sinceI₀ is maximal, we cannot add any vertex inV(G)\I₀ toI₀ while maintaining independence. Therefore, G has no independent set I^′ (̸=I₀) which is reachable from I₀, and henceI_sol =I₀.

We then consider the other case, that is, I₀ is not a maximal independent set of Gor|I₀|> l. Observe that it suffices to consider the only case where |I₀|> l holds;

if |I0| = l and I0 is not maximal, then we can obtain an independent set I₀^′′ of G such that |I₀^′′| =l+ 1 and I₀ ↭^l I₀^′′ by adding some vertex in V(G)\I₀. To prove I_sol =I_max, we below show that I₀ ↭^l I_max holds if |I₀|> l.