On (In)approximability of MaxMin Independent Set Reconfiguration

Our first contribution is an $(n/\log n)$-factor polynomial-time approximation algorithm for MMISR on general $n$-vertex graphs (Theorem 3.1). This is the first non-trivial approximation algorithm for MMISR, and complements the $\mathrm{𝖭𝖯}$-hardness of $n^{1-\epsilon }$-factor approximation [30, 49].

Our next contribution is to develop approximation algorithms for MMISR on special graph classes, by leveraging techniques from parameterised complexity. See Figure 1 for the relationships between graph parameters examined in this paper and Section 2 for the formal definitions of these parameters. First, we show a polynomial-time algorithm for $k$-degenerate graphs whose approximation factor is $\approx k$ (Theorem 3.2).

Second, for graphs of treewidth at most $k$, we show a polynomial-time approximation algorithm for MMISR whose approximation factor is $\approx \frac{\phi }{\phi -O(k\log \phi )}$, where $\phi$ is the input independent set size (Theorem 3.3), assuming that a tree decomposition of width $k$ is given as input. As an application of this algorithm, we show an $\mathrm{𝖥𝖯𝖳}$-approximation scheme (FPT-AS) parameterised by treewidth $k$ (Theorem 3.4); i.e., for every $\epsilon >0$, there exists a $(1+\epsilon )$-factor approximation algorithm that runs in time $f(k,\epsilon )\cdot n^{O(1)}$ for some computable function $f$. Our FPT-AS is obtained by combining Theorem 3.3 with an $\mathrm{𝖥𝖯𝖳}$ algorithm for MMISR, which is based on [1, 32]. Note that an FPT-AS implies an efficient polynomial-time approximation scheme (EPTAS) for each fixed $k$.³³3This is stronger than Theorem 3.2, which implies an $O(k)$-factor approximation algorithm since the degeneracy is bounded by the treewidth.

Third, we show an FPT-AS for $H$-minor-free graphs parameterised by the size of $H$ (Theorem 3.5). $H$-minor-free graphs form a subclass of bounded-degeneracy graphs [45] and include planar graphs and bounded-genus graphs. Specifically, for every $\epsilon >0$ and for graphs that exclude a fixed graph $H$ as a minor, there exists a $(1+\epsilon )$-factor approximation algorithm that runs in time $f(|V(H)|,\epsilon )\cdot n^{O(1)}$ for some computable function $f$.

Our last contribution is that we establish inapproximability results for MMISR on restricted graph classes. Specifically, we first prove the $\mathrm{𝖭𝖯}$-hardness of $\mathrm{\Theta }(\sqrt{\mathrm{\Delta }})$-factor approximation for graphs of maximum degree $\mathrm{\Delta }$ (Theorem 3.7). This hardness result is quantitatively stronger than the $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness of ${\mathrm{\Delta }}^{{\epsilon }_0}$-factor approximation [24], where ${\epsilon }_0$ may be extremely small (e.g., ${\epsilon }_0=0.001$). Then, we prove the $\mathrm{𝖭𝖯}$-hardness of $\mathrm{\Theta }\left(n^{4{\delta }^2-\epsilon }\right)$-factor approximation for $n$-vertex graphs of bandwidth $O\left(n^{\frac{1}{2}+\delta }\right)$, where $\delta \in (0,\frac{1}{2})$ is a positive real and $\epsilon$ is any small positive real (Theorem 3.8). This result means that for graphs of bandwidth, treewidth, and degeneracy $n^{\frac{1}{2}+\mathrm{\Theta }(1)}$, MMISR cannot be approximated within a polynomial factor in polynomial time unless $𝖯=\mathrm{𝖭𝖯}$. Finally, we prove that MMISR on $n$-vertex bipartite graphs cannot be approximated within a factor of $n^{1-\epsilon }$ for any $\epsilon >0$, assuming the Small Set Expansion Hypothesis (SSEH) [44] and $\mathrm{𝖭𝖯}⊈\mathrm{𝖡𝖯𝖯}$ (Theorem 3.9). Therefore, MMISR on bipartite graphs is as hard as on general graphs with respect to the approximation factor.

A natural question is whether our $(n/\log n)$-approximation can be improved by applying stronger static approximation algorithms for Maximum Independence Set (MIS) on general graphs (see an overview in Section 1.3 below). We do not know how to do this in a black-box manner. The main obstacle is that MMISR requires not just one large independent set but a reconfiguration sequence where every independent set is large throughout. By contrast, an approximation algorithm for MIS only returns a single large independent set, and it is not clear how to connect it with the prescribed initial and target sets such that all the independent sets throughout the reconfiguration process remain large. Therefore, improving the approximation factor for MMISR seems to require techniques that are aware of the reconfiguration rules.

Next, we compare our algorithmic and hardness results. Since the degeneracy is bounded by the maximum degree, Theorems 3.2 and 3.7 imply that the optimal approximation factor for MMISR on graphs of degeneracy $k$ lies between $\mathrm{\Theta }(\sqrt{k})$ and $\mathrm{\Theta }(k)$. Since the treewidth is bounded by the bandwidth, Theorems 3.4 and 3.8 imply that MMISR on graphs of treewidth $k$ admits an EPTAS if $k=O(1)$, while does not have a polynomial-factor approximation algorithm if $k=n^{\frac{1}{2}+\mathrm{\Theta }(1)}$. An immediate open question is thus if there exists an (E)PTAS for MMISR on graphs of superconstant treewidth $k$ (e.g., $k=\log n$).

The parameterised complexity of Independent Set Reconfiguration under the Token Jumping rule (ISR-TJ) is well-studied with respect to the independent set size $k$. On general graphs, ISR-TJ is known to be $𝖶$[1]-hard [31, 37] and $\mathrm{𝖷𝖫}$-complete [8]. As with the classical Independent Set problem, FPT algorithms for ISR-TJ have been developed for several sparse graph classes. Specifically, Bousquet, Mary and Parreau [9] showed that the problem is fixed-parameter tractable on biclique-free graphs, a wide class that encompasses planar graphs, bounded-degeneracy graphs, and nowhere dense graphs. For a comprehensive review of these and related results, we refer the reader to the recent survey by Bousquet, Mouawad, Nishimura and Siebertz [10].

For a reconfiguration problem, its approximate version allows to use infeasible solutions, but requires optimising the “worst” feasibility along the reconfiguration sequence. Ito, Demaine, Harvey, Papadimitriou, Sideri, Uehara, and Uno [30] showed that approximate versions of Independent Set Reconfiguration and SAT Reconfiguration are $\mathrm{𝖭𝖯}$-hard to approximate. Note that the reduction in [30] along with the inapproximability results of Maximum Independent Set due to Håstad [20] and Zuckerman [49] implies the $\mathrm{𝖭𝖯}$-hardness of $n^{1-\epsilon }$-approximation for any $\epsilon >0$. $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness of approximation for reconfiguration problems was posed as an open problem by [30]. Ohsaka [38] postulated a reconfiguration analogue of the PCP theorem [2, 3], called the Reconfiguration Inapproximability Hypothesis (RIH), and proved that assuming RIH, approximate versions of several reconfiguration problems are $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard to approximate, including MMISR. Recently, Hirahara and Ohsaka [25] and Guruswami, Karthik C. S., Manurangsi, Ren, and Wu [16] independently gave a proof of RIH, thereby resolving the open problem of [30] affirmatively. Ohsaka [42] also gave an alternative proof of RIH.

Since the resolution of RIH, the following results have been obtained on the hardness of approximating MMISR: Ohsaka [38] showed that MMISR on graphs of maximum degree $3$ is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard to approximate within a constant factor. Hirahara and Ohsaka showed that MMISR on $n$-vertex graphs is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard to approximate within a factor of $n^{\mathrm{\Omega }(1)}$ [25], and MMISR on graphs of maximum degree $\mathrm{\Delta }$ is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard to approximate within a factor of ${\mathrm{\Delta }}^{\mathrm{\Omega }(1)}$ [24, Theorem 3.4]. In this paper, we improve the known inapproximability factors for MMISR quantitatively.

Approximation algorithms and inapproximability results have also been studied for other reconfiguration problems, including 2-CSP Reconfiguration [16, 39, 40, 41], Set Cover Reconfiguration [16, 24], $k$-Colouring Reconfiguration [27], $k$-SAT Reconfiguration [26], Subset Sum Reconfiguration [29], and Submodular Reconfiguration [43].

For the classical Maximum Independent Set (MIS) problem, it is $\mathrm{𝖭𝖯}$-hard to approximate within a factor of $n^{1-\epsilon }$ for any $\epsilon >0$ [20, 49], while the best algorithm by Feige [14] achieves the approximation factor of $O\left(\frac{n{(\log \log n)}^2}{{(\log n)}^3}\right)$. For graphs with maximum degree $\mathrm{\Delta }$, it is hard to approximate within a factor of $O\left(\frac{\mathrm{\Delta }}{{(\log \mathrm{\Delta })}^2}\right)$ [6], while there exists $O\left(\frac{\mathrm{\Delta }\log \log \mathrm{\Delta }}{\log \mathrm{\Delta }}\right)$-approximation algorithm [19]. On planar graphs, Baker [5] showed a PTAS, and this has later been generalised into a PTAS for $H$-minor-free graphs [12].

$\mathrm{𝖥𝖯𝖳}$-approximation schemes are a common approach in parameterised approximation, which combines the techniques from parameterised complexity and approximation in order to overcome the hardness in both paradigms. See the surveys by Marx [35] and by Feldmann, Karthik C. S., Lee, and Manurangsi [15].

Our main result for general graphs is as follows.

To obtain an $(n/\log n)$-factor approximation algorithm, we introduce the notion of a $\gamma$-sequence for a nonnegative integer $\gamma$. Given an instance $(G,I_{\mathrm{ini}},I_{\mathrm{tar}})$ of MMISR, a $\gamma$-sequence $𝒮=(I^{(1)},I^{(2)},\mathrm{\dots },I^{(t)})$ is a sequence of independent sets of size at least $\gamma$ such that the following procedure yields a reconfiguration sequence from $I_{\mathrm{ini}}$ to $I_{\mathrm{tar}}$. (1) Remove vertices from $I_{\mathrm{ini}}$ to obtain $I^{(1)}$. (2) For each $i=1,2,\mathrm{\dots },t-1$, first add the vertices in $I^{(i+1)}\setminus I^{(i)}$ to obtain $I^{(i)}\cup I^{(i+1)}$, and then remove the vertices in $I^{(i)}\setminus I^{(i+1)}$ to obtain $I^{(i+1)}$. (3) Add vertices to $I^{(t)}$ to obtain $I_{\mathrm{tar}}$. We therefore require that $I^{(i)}\cup I^{(i+1)}$ is an independent set of $G$ for every $i$, so that all intermediate sets in the above procedure are feasible. The formal definition is given in Section 4. By definition, the existence of a $\gamma$-sequence implies a reconfiguration sequence from $I_{\mathrm{ini}}$ to $I_{\mathrm{tar}}$ of value at least $\gamma$.

Now consider an arbitrary partition of the vertex set $V(G)$ into disjoint subsets $V_1,V_2,\mathrm{\dots },V_{\mathrm{\ell }}$ of equal size for some $\mathrm{\ell }$ that we can choose later. Then we can show the existence of a $\gamma$-sequence $𝒮$ such that each element of $𝒮$ is a subset of some (not necessarily the same) $V_j$, and $𝒮$ yields an $\mathrm{\ell }$-factor approximation. Specifically, the idea of this existence proof is that for each set in an optimal sequence, we select an index $j$ such that the size of its intersection with $V_j$ is maximised. By concatenating all such intersections, we obtain the desired $\gamma$-sequence.

Next, our approach to find a $\gamma$-sequence as described above is to create an auxiliary graph $H_{\gamma }$ for each value $\gamma \in \{0,1,\mathrm{\dots },n/\mathrm{\ell }\}$. (Note that $n/\mathrm{\ell }$ is the size of every $V_i$.) The vertices of $H_{\gamma }$ are all the independent sets $I\subseteq V_i$ of $G$ with $|I|\ge \gamma$ for some $i\in [\mathrm{\ell }]$. Two such sets are connected by an edge in $H_{\gamma }$ if and only if their union is an independent set of $G$. A desired $\gamma$-sequence then corresponds to a path in $H_{\gamma }$ from a subset of $I_{\mathrm{ini}}$ to a subset of $I_{\mathrm{tar}}$, and we choose the maximum $\gamma \in \{0,1,\mathrm{\dots },n/\mathrm{\ell }\}$ for which such a path exists.

In order to find this path in polynomial time, we want $H_{\gamma }$ to have polynomial size. Since each $V_i$ has $2^{n/\mathrm{\ell }}$ subsets, we choose $\mathrm{\ell }=n/\log n$. We then obtain the approximation factor of $n/\log n$ as discussed above.

We now sketch the algorithm for the following result.

Suppose $G$ is $d$-degenerate; that is, every induced subgraph of $G$ contains a vertex of degree at most $d$. The main idea of our algorithm is as follows. We maintain two independent sets $A$ and $B$, where initially $A≔I_{\mathrm{ini}}$ and $B≔I_{\mathrm{tar}}$. We reconfigure $A$ or $B$ in order to increase the size of $A\cap B$. In particular, let $X≔A\setminus B$ and $Y≔B\setminus A$. Since $G$ is $d$-degenerate, in the subgraph of $G$ induced on $X\cup Y$, there is a vertex $v$ that has degree at most $d$. If $v\in X$, we remove the neighbours of $v$ in $B$ from $B$ and add $v$ to $B$. Note that the neighbours of $v$ in $B$ have to be in $Y$, since the vertices in $B\setminus Y$ are also in $A$ and hence are not adjacent to $v$. In other words, we remove at most $d$ vertices from $B$ and add exactly one vertex to $B$. If $v\in Y$, we analogously remove at most $d$ neighbours of $v$ in $A$ from $A$ and add $v$ to $A$. Note that after every iteration, we remove at least one vertex from $X\cup Y$. Hence, eventually, we have $A=B$. We can then combine the reconfiguration sequence for $A$ and the reversed reconfiguration sequence for $B$ to obtain a reconfiguration sequence from $I_{\mathrm{ini}}$ to $I_{\mathrm{tar}}$.

The algorithm clearly runs in polynomial time. To analyse the approximation factor, observe that at every step in the reconfiguration sequence for $A$, we remove at most $d$ vertices from $A$ and add exactly one vertex to $A$. Consequently, after $i$ steps, the size of $A$ decreases by at most $(d-1)i$. On the other hand, exactly $i$ vertices have been added to $A$ during these $i$ steps. Hence, after $i$ steps, the size of the independent set $A$ is at least $\max \{|I_{\mathrm{ini}}|-(d-1)i,i\}\ge \frac{1}{d}|I_{\mathrm{ini}}|$. This implies all independent sets in the reconfiguration sequence for $A$ have size at least $\frac{1}{d}|I_{\mathrm{ini}}|$. Similarly, all independent sets in the reconfiguration sequence for $B$ have size at least $\frac{1}{d}|I_{\mathrm{tar}}|$. Since the optimal value is at most $\min \{|I_{\mathrm{ini}}|,|I_{\mathrm{tar}}|\}$, the algorithm achieves an approximation factor of $d$.

Suppose $G$ has treewidth $k$. We assume that a tree decomposition of width $k$ is given; otherwise, this can be computed in $\mathrm{𝖥𝖯𝖳}$ time [7]. Further, let $\phi =\min \{|I_{\mathrm{ini}}|,|I_{\mathrm{tar}}|\}$. We now discuss the main idea of the $\frac{\phi }{\phi -O(k\log \phi )}$-approximation algorithm. This approach relies on the fact that there exists a $\frac{2}{3}$-balanced $I_{\mathrm{ini}}$-separator $S$ of size at most $k+1$ [11], i.e., we can partition $V(G)\setminus S$ into two sets $X$ and $Y$ such that there are no edges between $X$ and $Y$, $|X\cap I_{\mathrm{ini}}|\le \frac{2}{3}|I_{\mathrm{ini}}|$, and $|Y\cap I_{\mathrm{ini}}|\le \frac{2}{3}|I_{\mathrm{ini}}|$. We then remove the vertices in $I_{\mathrm{ini}}\cap S$, recurse on $X$ and $Y$ in some suitable order, and finally add $I_{\mathrm{tar}}\cap S$. Since $|X\cap I_{\mathrm{ini}}|$ and $|Y\cap I_{\mathrm{ini}}|$ are at most $\frac{2}{3}|I_{\mathrm{ini}}|$, the recursion depth is $O(\log \phi )$, and hence the overall runtime is polynomial. We then carefully analyse the size of the smallest independent set obtained from the recursion, using the order of processing $X$ and $Y$ as well as the bounds on $|S|$, $|X\cap I_{\mathrm{ini}}|$, and $|Y\cap I_{\mathrm{ini}}|$. For this, we obtain the following result.

Next, for the $\mathrm{𝖥𝖯𝖳}$-approximation scheme, we aim to obtain a $(1+\epsilon )$-factor approximation in time $f(k,\epsilon )\cdot n^{O(1)}$ for any $\epsilon >0$ and some computable function $f$. If the $\frac{\phi }{\phi -O(k\log \phi )}$-approximation algorithm above already achieves this guarantee, we use it. Otherwise, $\phi$ must be bounded from above by a function of $k$ and $\epsilon$. We now apply an $\mathrm{𝖥𝖯𝖳}$ algorithm to solve MMISR exactly parameterised by $\phi$ and $k$ (see [28, Theorem 5.8]), which is also an $\mathrm{𝖥𝖯𝖳}$ algorithm parameterised by $k$ and $\epsilon$ in this case. In order to obtain this $\mathrm{𝖥𝖯𝖳}$ algorithm, we first extend the equivalence between the Token Jumping rule and Token Addition/Removal rule of ISR [32] to an equivalence between ISR under the Token Jumping rule (ISR-TJ) and MMISR. We then derive the $\mathrm{𝖥𝖯𝖳}$ algorithm above from a recent $\mathrm{𝖥𝖯𝖳}$ algorithm for ISR-TJ parameterised by degeneracy and the size of the input independent sets [1]. Overall, we obtain the following $\mathrm{𝖥𝖯𝖳}$-approximation scheme.

For these graphs, we also have an $\mathrm{𝖥𝖯𝖳}$-approximation scheme.

Suppose that $|I_{\mathrm{ini}}|=|I_{\mathrm{tar}}|$ and let $\eta ≔|I_{\mathrm{ini}}|$. We employ a generalisation of Baker’s technique, which is a framework for developing polynomial-time approximation schemes (PTASs) for various problems on planar graphs [5]. It is known that the vertex set of any planar graph $G$ can be partitioned into $V_1,V_2,\mathrm{\dots },V_{k+1}$ such that, for each $i\in [k+1]$, the subgraph $G_i$ induced by $V(G)\setminus V_i$ has bounded treewidth. Moreover, by the pigeonhole principle, there is an integer $j\in [k+1]$ such that $\max \{|I_{\mathrm{ini}}\cap V_j|,|I_{\mathrm{tar}}\cap V_j|\}\le \frac{2\eta }{k+1}$, which implies that $\phi ≔\min \{|I_{\mathrm{ini}}\cap V(G_j)|,|I_{\mathrm{tar}}\cap V(G_j)|\}\ge \left(1-\frac{2}{k+1}\right)\eta$.

The high-level idea of our algorithm is as follows: first remove the vertices in $V_j\cap I_{\mathrm{ini}}$ from $I_{\mathrm{ini}}$, then apply the $\mathrm{𝖥𝖯𝖳}$-approximation scheme for bounded-treewidth graphs to $G_j$, and finally add the vertices in $V_j\cap I_{\mathrm{tar}}$. By appropriately setting $k$ and using the bound $\phi \ge \left(1-\frac{2}{k+1}\right)\eta$, this yields an $\mathrm{𝖥𝖯𝖳}$-approximation scheme for planar graphs. A similar argument can be established for $H$-minor-free graphs by using the decomposition theorem of Demaine, Hajiaghayi, and Kawarabayashi [12].

Let $I_G$ be any maximum independent set of $G$, where $|I_G|=\alpha (G)$. Consider a reconfiguration sequence $𝒮$ from $I_{\mathrm{ini}}$ to $I_{\mathrm{tar}}$, passing through $I_G$, obtained by the following procedure:

Step 1.

add all $\alpha (G)$ vertices of $I_G$ to obtain $L\cup I_G$.

Step 2.

remove all $k$ vertices of $L$ to obtain $I_G$.

Step 3.

add all $k$ vertices of $R$ to obtain $R\cup I_G$.

Step 4.

remove all $\alpha (G)$ vertices of $I_G$ to obtain $R$.

Observe that the objective value of $𝒮$ is at least $\min \{|L|,|R|,\alpha (G)\}$, and thus so is ${\mathrm{𝗈𝗉𝗍}}_H(I_{\mathrm{ini}}\leftrightsquigarrow I_{\mathrm{tar}})$.

On the other hand, let ${𝒮}^{\ast }$ be an optimal reconfiguration sequence from $I_{\mathrm{ini}}$ to $I_{\mathrm{tar}}$. Since $K$ is a complete bipartite graph with bipartition $(I_{\mathrm{ini}},I_{\mathrm{tar}})=(L,R)$, there must exist an independent set $I$ in ${𝒮}^{\ast }$ such that $I\cap (L\cup R)=\mathrm{\varnothing }$, implying that $|I|=|I\cap V(G)|\le \alpha (G)$. Therefore, the objective value of ${𝒮}^{\ast }$ is at most $\min \{|L|,|R|,\alpha (G)\}$, and thus so is ${\mathrm{𝗈𝗉𝗍}}_H(I_{\mathrm{ini}}\leftrightsquigarrow I_{\mathrm{tar}})$. $◀$

Recall that it is $\mathrm{𝖭𝖯}$-hard to distinguish whether $\alpha (G)\ge n^{1-\epsilon }$ or $\alpha (G)\le n^{\epsilon }$ for any small $\epsilon >0$ [20, 49]. By applying ˜3.6 with $k≔n$, it is $\mathrm{𝖭𝖯}$-hard to distinguish whether ${\mathrm{𝗈𝗉𝗍}}_H(I_{\mathrm{ini}}\leftrightsquigarrow I_{\mathrm{tar}})\ge n^{1-\epsilon }=\mathrm{\Theta }({|V(G)|}^{1-\epsilon })$ or ${\mathrm{𝗈𝗉𝗍}}_H(I_{\mathrm{ini}}\leftrightsquigarrow I_{\mathrm{tar}})\le n^{\epsilon }=\mathrm{\Theta }({|V(G)|}^{\epsilon })$ for any small $\epsilon >0$. Therefore, MMISR on $n$-vertex graphs is $\mathrm{𝖭𝖯}$-hard to approximate within a factor of $n^{1-\epsilon }$, as desired.

Consider now proving the $\mathrm{𝖭𝖯}$-hardness of approximating MMISR on restricted graph classes. To this end, we modify the above gap-preserving reduction from MIS to MMISR as follows:

(Maximum degree $\mathrm{\Delta }$)

By [6], it is $\mathrm{𝖭𝖯}$-hard to approximate MIS on graphs $G$ of maximum degree $\mathrm{\Delta }$ within a factor of $\frac{\mathrm{\Delta }}{polylog(\mathrm{\Delta })}$. We shall apply ˜3.6 with $k={\mathrm{\Theta }}_{\mathrm{\Delta }}(n)$; however, this makes the degree of the bipartite graph $K$ (constructed in the above reduction) too large. To avoid this issue, we replace $K$ by a $\mathrm{\Delta }$-regular bipartite Ramanujan graph $X$. Informally speaking, bipartite Ramanujan graphs behave like random bipartite graphs. By the bipartite expander mixing lemma [17, 18], we show that $X$ does not contain independent sets of size $\mathrm{\Omega }\left(\frac{k}{\sqrt{\mathrm{\Delta }}}\right)$, which allows us to create a $\sqrt{\mathrm{\Delta }}$-factor gap.

Theorem 3.7.

For a graph of maximum degree $\mathrm{\Delta }\ge 3$, it is $\mathrm{𝖭𝖯}$-hard (under randomised reductions) to approximate MMISR within a factor of $\mathrm{\Theta }\left(\sqrt{\mathrm{\Delta }}\right)$.

(Bandwidth $n^{\frac{1}{2}+\delta }$)

By [20], we first show that for an $n$-vertex graph $G$ of bandwidth $n^{\frac{1}{2}+\delta }$, it is $\mathrm{𝖭𝖯}$-hard to approximate $\alpha (G)$ within a factor of $\approx n^{4{\delta }^2}$. By applying ˜3.6 with $k\approx n^{\frac{1}{2}+\delta }$, we obtain the $\mathrm{𝖭𝖯}$-hardness of approximating MMISR on graphs of bandwidth $n^{\frac{1}{2}+\delta }$ within the same factor.

Theorem 3.8.

Let $\delta \in (0,\frac{1}{2})$ be any positive real and $\epsilon \in (0,\frac{1}{2}-\delta )$ be any small positive real. For an $n$-vertex graph of bandwidth $O\left(n^{\frac{1}{2}+\delta }\right)$, it is $\mathrm{𝖭𝖯}$-hard to approximate MMISR within a factor of $\mathrm{\Theta }\left(n^{4{\delta }^2-\epsilon }\right)$.

(Bipartite graphs)

Instead of using the above reduction, we show the “equivalence” (up to a constant factor) between Maximum Balanced Biclique and MMISR on bipartite graphs. Since this problem cannot be approximated within a factor of $n^{1-\epsilon }$ under SSEH and $\mathrm{𝖭𝖯}⊈\mathrm{𝖡𝖯𝖯}$ [34], where $n$ is the number of vertices in an input graph, MMISR cannot be approximated within the same factor.

Theorem 3.9.

Assuming SSEH and $\mathrm{𝖭𝖯}⊈\mathrm{𝖡𝖯𝖯}$, for an $n$-vertex bipartite graph, no polynomial-time algorithm can approximate MMISR within a factor of $n^{1-\epsilon }$ for any $\epsilon >0$.