QPTAS for MWIS and Finding Large Sparse Induced Subgraphs in Graphs with Few Independent Long Holes

First, in time $𝒪({|V(G)|}^t)$ we exhaustively check whether $G$ has an induced cycle with exactly $t$ vertices. If such a cycle exists, we return it as it is clearly shortest possible.

Next, for every tuple $\tau$ of $t$ distinct vertices of $G$ we check whether $\tau$ induces a path. Suppose this is the case and let $x,y$ the endvertices of this path. We remove from $G$ the closed neighborhood of all internal vertices of the path, except for $x$ and $y$. Finally, we search for a shortest path connecting $x$ and $y$ in the obtained graph; together with the vertices from $\tau$ it forms an induced cycle with at least $t$ vertices. We return the shortest of all cycles found in this process, or report that no cycle was found. $◀$

Finally, let us recall a result that is particularly useful for constructing QPTASes for MWIS. A vertex $v$ of a weighted graph $(G,𝗐)$ is $\gamma$-heavy with respect to a set $I\subseteq V(G)$ if $𝗐(N_G[v]\cap I)⩾\gamma \cdot 𝗐(I)$.

Intuitively, Lemma 4 is a quasipolynomial approximation-preserving reduction to instances without $\gamma$-heavy vertices: we can exhaustively guess $I^{\prime }\in {ℐ}^{\prime }$ and delete $N[I^{\prime }]$ from the graph.

Fix $s$ and $t$. Since the value of $t$ will be fixed throughout the whole proof, by a long hole we mean an induced cycle with at least $t$ vertices. We denote such a long hole shortly by $C_{⩾t}$.

Let $(G,𝗐)$ be a weighted graph on $n$ vertices. Let $\epsilon >0$ be the desired precision, i.e., we aim for an $(1-\epsilon )$-approximation or for finding an induced subgraph isomorphic to $s{C}_{⩾t}$.

The algorithm is a typical recursive branching algorithm. Each recursive call is invoked for an induced subgraph $G^{\prime }$ of $G$ and an integer $s^{\prime }⩽s$; the goal is to either exhibit an induced $s^{\prime }{C}_{⩾t}$ subgraph of $G^{\prime }$ or an independent set $I^{\prime }$ of weight close to $\alpha (G^{\prime },𝗐)$ (the actual error analysis is made formally later; it is not just merely an $(1-\epsilon )$-approximation to $\alpha (G^{\prime },𝗐)$). The initial call is to $G^{\prime }=G$ and $s^{\prime }=s$.

We set

The computation of one recursive call is embedded in the following claim.

We now argue how Claim 5 yields Theorem 1. Consider a recursive call with parameters $(G^{\prime },s^{\prime })$. If $s^{\prime }=0$, then we return $\mathrm{\varnothing }$ as an induced $s^{\prime }{C}_{⩾t}$. If $V(G^{\prime })=\mathrm{\varnothing }$, we return the empty (independent) set.

Otherwise, we apply Claim 5 to $G^{\prime }$ and $s^{\prime }$. If an induced $s^{\prime }{C}_{⩾t}$ is returned, we return it and conclude. Otherwise, we iterate over the obtained family $𝒳$. For every $(X,J)\in 𝒳$, let ${𝒟}_X$ be the set of connected components of $G^{\prime }-X$. For every $D\in {𝒟}_X$, we recurse on $G_D^{\prime }≔G^{\prime }[D]$ and either $s_D^{\prime }≔s^{\prime }$ if $|D|⩽\frac{5}{6}|V(G^{\prime })|$ (Property 2b) or $s_D^{\prime }≔s^{\prime }-1$ otherwise. If an induced $s_D^{\prime }{C}_{⩾t}$ is returned in $G_D^{\prime }$, we augment it with a $C_{⩾t}$ non-adjacent to $D$ in $G^{\prime }$ if $s_D^{\prime }=s^{\prime }-1$ (such a long hole can be found using Lemma 3) and return. Otherwise, if an independent set $I_D^{\prime }$ is returned, we compute an independent set $I_{(X,J)}={\bigcup }_{D\in {𝒟}_X}{I}_D^{\prime }\cup J$ (Note that this is an independent set due to condition $N[J]\subseteq X$.) Finally, if no $s^{\prime }{C}_{⩾t}$ was returned for any $(X,J)\in 𝒳$, we return $I_{(X,J)}$ of maximum weight among all options $(X,J)\in 𝒳$. This completes the description of the algorithm.

Let us move to the analysis. For a recursive call $(G^{\prime },s^{\prime })$, let

Observe that every recursive subcall $(G_D^{\prime },s_D^{\prime })$ satisfies $\mu (G_D^{\prime },s_D^{\prime })⩽\mu (G^{\prime },s^{\prime })-1$. Hence, the depth of the recursion is bounded by $s+\lfloor {\log }_{6/5}n\rfloor$. Since every recursive call results in $n^{𝒪(\log n/\gamma )}$ subcalls, the overall running time is as follows:

i.e., quasipolynomial in $n$ (we hide terms depending on $s$ and $t$ in the $𝒪(\cdot )$-notation).

Clearly, if any recursive call $(G^{\prime },s^{\prime })$ finds an induced $s^{\prime }{C}_{⩾t}$, it is propagated up in the recursion tree and results in exhibiting an induced $s{C}_{⩾t}$ in the root call. Assume then that every recursive call $(G^{\prime },s^{\prime })$ returned an independent set, which we denote $I_{G^{\prime },s^{\prime }}$.

Consider a recursive call $(G^{\prime },s^{\prime })$ and let $I^{\prime }$ be an independent set in $G^{\prime }$ of weight $\alpha (G^{\prime },𝗐)$. By the promise of Claim 5, there exists $(X,J)\in 𝒳$ in this recursive call with $J\subseteq I^{\prime }$ and $𝗐((X\setminus J)\cap I^{\prime })⩽\beta \alpha (G^{\prime },𝗐)=\beta 𝗐(I^{\prime })$. In particular, $\alpha (G^{\prime }-X,𝗐)⩾(1-\beta )\alpha (G^{\prime },𝗐)$. By a standard induction on the depth of the subtree of the recursion tree, we obtain that if the depth of the recursion tree of a call $(G^{\prime },s^{\prime })$ is $h$, then $𝗐(I_{G^{\prime },s^{\prime }})⩾{(1-\beta )}^h\alpha (G^{\prime },𝗐)$. In particular, since the recursion depth at the root is bounded by $s+\lfloor {\log }_{6/5}n\rfloor$, the root call returns an independent set of weight at least

Thus, it remains to prove Claim 5.

Let $I^{\prime }$ be an independent set in $G^{\prime }$ of weight $\alpha (G^{\prime },𝗐)$.

We start with a standard application of Lemma 4. We enumerate the family ${ℐ}_0$ of $n^{𝒪(\log n/\gamma )}$ independent sets in $G^{\prime }$ such that there exists $I_0\in {ℐ}_0$ such that $I_0\subseteq I^{\prime }$ and every $\gamma$-heavy vertex with respect to $I^{\prime }$ belongs to $N[I_0]$. Henceforth, we will refer to this choice of $I_0$ as the correct choice of $I_0$.

Initiate $𝒳=\mathrm{\varnothing }$. We iterate over the elements of ${ℐ}_0$. For every $I_0\in {ℐ}_0$ we proceed as follows. Let $X_0≔N_{G^{\prime }}[I_0]$ and $G_0≔G^{\prime }-X_0$.

We find a shortest long hole in $G_0$ by Lemma 3. If Lemma 3 reports that $G_0$ is $C_{⩾t}$-free, we invoke the exact quasipolynomial-time algorithm of [17] that finds in time $n^{𝒪({\log }^{4}n)}$ an independent set $J$ of maximum weight in $G_0$. We insert $(V(G^{\prime }),I_0\cup J)$ into $𝒳$ and conclude computation for $I_0$. Note that for the correct choice of $I_0$, we have $𝗐(I_0\cup J)=\alpha (G^{\prime },𝗐)$.

Assume then that Lemma 3 returns a long hole $H$. If $|V(H)|⩽2t+8$, then, assuming the correct choice of $I_0$, we have

Hence, we can insert $(X≔X_0\cup N_{G_0}[V(H)],I_0)$ into $𝒳$ and conclude the computation for the current $I_0$, as then $G^{\prime }-X$ is non-adjacent to $H$, so every connected component of $G^{\prime }-X$ satisfies Property 2a.

Therefore, from now on, we assume that $|V(H)|>2t+8$.

Assume $v$ fails at realizing the latter condition. Then there is a $(t-1)$-vertex subpath $P$ of $H$, disjoint from the neighborhood of $v$. Let $u\ne u^{\prime }\in V(H)$ be such that $u$ and $u^{\prime }$ are neighbors of $v$, and delimit a subpath $P^{\prime }$ of $H$ containing $P$ and containing only two neighbors of $v$ (its endpoints $u$ and $u^{\prime }$). Observe that if $v$ has at most one neighbor in $V(H)$, it readily satisfies the first condition of the claim. For $V(P^{\prime })\cup \{v\}$ not to contradict that $H$ is a shortest long hole of $G$, vertices $u$ and $u^{\prime }$ have to be at distance at most 2 in $H$ (along the other subpath of $H$ delimited by $u$ and $u^{\prime }$), and so $v$ satisfies the first condition. $\mathrm{⊲}$

We first get rid of the vertices satisfying the second condition of Claim 6. Let $P$ be a subpath of $H$ with $t-1$ vertices. We set $X_1≔N_{G_0}(P)\setminus V(H)$ and let $G_1$ be the connected component of $G_0\setminus X_1$ that contains $H$.

We will insert $X_0\cup X_1$ into any output set $X$ in what follows, so one may think of this step as deleting the vertices of $X_1$. Every connected component of $G_0\setminus X_1$ except for $G_1$ satisfies Property 2a, so we need only to focus on $G_1$.

As $|V(P)|=t-1$, assuming the correct choice of $I_0$, we have

Note that every vertex satisfying the second condition of Claim 6 lies in $X_1$.

Let us now consider BFS layering from $H$ in $G_1$ with layers $V(H)=L_0,L_1,L_2,\mathrm{\dots },L_h$. If $h⩽\lceil \frac{5}{\beta }\rceil$, we set $h^{\prime }≔h+1$, and otherwise we iterate over all options of $1⩽h^{\prime }⩽\lceil \frac{5}{\beta }\rceil$. In both cases, there exists a choice of $h^{\prime }$ with $𝗐(I^{\prime }\cap L_{h^{\prime }})⩽\frac{\beta }{5}𝗐(I^{\prime })$; we call it henceforth the correct choice of $h^{\prime }$. For fixed $h^{\prime }$, we set $X_2≔L_{h^{\prime }}$ and $G_2≔G_1[{\bigcup }_{i=0}^{h^{\prime }-1}{L}_i]$. Note that $G_2$ is connected and every connected component of $G_1-X_2$ distinct from $G_2$ lies in ${\bigcup }_{i>h^{\prime }}{L}_i$ and, consequently, is non-adjacent to $H$ and therefore satisfies point 2a. Hence, in what follows we will insert $X_2$ into any returned set $X$ and we focus on $G_2$.

Note that $ℒ≔L_0,L_1,\mathrm{\dots },L_{h^{\prime }-1}$ is the BFS layering in $G_2$ from $H$. The following claims and definitions refer to $G_2$.

For , a vertical path between $u\in L_i$ and $v\in L_j$ with respect to $ℒ$ is a path $P$ such that $V(P)$ intersects exactly once every layer $L_k$ such that $k\in [i,j]$, and no other layer. The cone of a vertex $v\in V(G_2)$ (still with respect to $ℒ$) is the set of vertices

Let $x$, $y$, $L_p$, $L_q$, $\mathrm{\ell }$, $x_1$, $y_1$ and $P$ be as in the claim statement.

Let $Q_x$ and $Q_y$ be two vertical paths from $x$ and $y$ to $x_1$ and $y_1$, respectively. Let $x_2$ and $y_2$ be the penultimate vertices of $Q_x$ and $Q_y$, respectively. Note that $x_2,y_2\in L_1$ and if $p=1$, then $x_2=x$ and $y_2=y$. Let $R$ be the shortest path in $G_2[V(P)\cup V(Q_x)\cup V(Q_y)\setminus \{x_1,y_1\}]$ connecting $x_2$ and $y_2$. Note that $R$ is non-adjacent to $H$ except for the endpoints. Furthermore, $|E(R)|⩽(p-1)+(q-1)+\mathrm{\ell }$.

Let $A$ and $B$ be the two subpaths of $H$ connecting $x_1$ and $y_1$. Without loss of generality, we assume that $|E(A)|⩾|E(B)|$. As $|V(H)|>2t+8$, we have $|E(A)|⩾t+5$.

Let $x_3$ and $y_3$ be the neighbors of $x_2$ and $y_2$ on $A$, respectively, such that no vertex of $A$ between $x_3$ and $y_3$ is adjacent to neither $x_2$ nor $y_2$. Let $A^{\prime }$ be the subpath of $A$ from $x_3$ to $y_3$. Since the neighborhood in $H$ of a vertex from $L_1$ is contained in a subpath of at most three consecutive vertices (by Claim 6), we have $|E(A^{\prime })|⩾|E(A)|-4⩾t$.

We now consider a cycle $H^{\prime }$ that is a concatenation of $x_2{x}_3$, $A^{\prime }$, $y_3{y}_2$, and $R$. Note that $H^{\prime }$ is an induced cycle in $G_2$. As $|E(A^{\prime })|⩾t$, $H^{\prime }$ is a long hole. As $H$ is the shortest hole of length at least $t$, we have

Hence, $|E(B)|⩽p+q+\mathrm{\ell }$. This completes the proof. $\mathrm{⊲}$

Let $Z$ be the union of the cones of $x$ and $y$. By Claim 7, any two vertices, one belonging to the cone of $x$ and another to the cone of $y$ respectively, in $Z$ lie within distance at most $p+q+\mathrm{\ell }$ along $H$. Hence, $Z$ lies in the subpath of $H$ with at most $2(p+q+\mathrm{\ell })$ vertices. $\mathrm{⊲}$

In the further proof, we use the following two corollaries of Claim 8:

For every $u\in V(H)$, let $D(u)\subseteq V(G_2)$ be the vertices whose cone contains $u$. Let $u_0,u_1,\mathrm{\dots },u_{|V(H)|-1}$ be a numbering of the vertices of $H$ along the hole $H$. We set

As $p⩽h^{\prime }⩽\lceil \frac{5}{\beta }\rceil$, so . The following claim is a direct consequence of Claim 9.

The removal of $D_{a,b}\cup D_{a^{\prime },b}$ disconnects $G$, provided $D_{a,b}$ and $D_{a^{\prime },b}$ are disjoint.

Let $G_3≔G_2-(D_{a,b}\cup D_{a^{\prime },b})$, and assume without loss of generality that . We want to argue that $G_3$ is disconnected. By Claim 10, no vertex of $V(G_3)\cap {\bigcup }_{j\in [a+b,a^{\prime }-1]}D(u_j)$ can be adjacent to a vertex of $V(G_3)\cap {\bigcup }_{j\in [0,a-1]\cup [a^{\prime }+b,|V(H)|-1]}D(u_j)$. Thus in particular $u_{a+b}$ and $u_{a^{\prime }+bmod|V(H)|}$ are in distinct connected components of $G^{\prime }$. $\mathrm{⊲}$

Let $n_2≔|V(G_2)|$. Fix $0⩽a_1⩽a_2⩽|V(H)|-1$ minimizing $a_2-a_1$ subject to

Observe that $a_1=a_2$ or

We set $d≔2b\cdot \lceil \frac{5}{\beta }\rceil$, and distinguish two cases: $a_2-a_1⩽d$ or $a_2-a_1>d$.

Let us consider the family of sets

By Claim 11, the $\lceil \frac{5}{\beta }\rceil$ sets of ${ℱ}_3$ are pairwise disjoint, thus there exists $X_3\in {ℱ}_3$ such that $𝗐(X_3\cap I^{\prime })⩽\frac{\beta }{5}𝗐(I^{\prime })$. For the same reason, there exists

such that $𝗐(X_4\cap I^{\prime })⩽\frac{\beta }{5}𝗐(I^{\prime })$. We iterate over all choices of $X_3$ and $X_4$. Finally, we exploit the fact that $a_2-a_1$ is small by adding $X_5≔{\bigcup }_{j\in [a_1,a_2]}N(u_j)$ to the set of vertices to remove. As $d\cdot \gamma ⩽\frac{\beta }{5}$, for the correct choices of $I_0$ and $h^{\prime }$ we have $𝗐(X_5\cap I^{\prime })⩽\frac{\beta }{5}𝗐(I^{\prime })$. We define $X≔X_0\cup X_1\cup X_2\cup X_3\cup X_4\cup X_5$ and insert $(X,I_0)$ into $𝒳$. We have $𝗐(X\cap (I^{\prime }\setminus I_0))⩽\beta 𝗐(I^{\prime })$.

We already argued that the connected components of $G^{\prime }-X$ disjoint from $V(G_2)$ satisfy Property 2a. By Claim 12, $G_2-(X_3\cup X_4\cup X_5)$ has two sets of connected components: those intersecting ${\bigcup }_{j\in [a_1,a_2]}D(u_j)$, and those not. The former kind are not adjacent to $H$, so satisfy Property 2a. The latter kind has at most $5n_2/6⩽5|V(G^{\prime })|/6$ vertices, by design of the interval $[a_1,a_2]$ using (1), so satisfy Property 2b.

Recall that by (2) we have . Then ${\bigcup }_{j\in [a_1-d,a_1-1]}D(u_j)$ and ${\bigcup }_{j\in [a_2+1,a_2+d]}D(u_j)$ contains each less than $n_2/6$ vertices, by the minimality of $a_2-a_1$. Hence . By the pigeonhole principle, as $d=2b\cdot \lceil \frac{5}{\beta }\rceil$, there is $a\in \{a_1-d,a_1-d+2b,\mathrm{\dots },a_1-2b\}$ (resp., $a^{\prime }\in \{a_2+2b,a_2+4b,\mathrm{\dots },a_2+d\}$) such that $𝗐(D_{a,b}\cap I^{\prime })⩽\frac{\beta }{5}𝗐(I^{\prime })$ (resp., $𝗐(D_{a^{\prime },b}\cap I^{\prime })⩽\frac{\beta }{5}𝗐(I^{\prime })$). We iterate over all choices of $a$ and $a^{\prime }$ and set $X_3≔D_{a,b}$, $X_4≔D_{a^{\prime },b}$. We take $X≔X_0\cup X_1\cup X_2\cup X_3\cup X_4$ and insert $(X,I_0)$ into $𝒳$. For the correct choice of $I_0$, $h^{\prime }$, $a$, $a^{\prime }$ we have $𝗐(X\cap (I^{\prime }\setminus I_0))⩽\beta 𝗐(I^{\prime })$.

Observe finally that $G_2-(X_3\cup X_4)$ has no connected component of size larger than $2n_2/3$, hence larger than $5|V(G^{\prime })|/6$. This completes the proof of Claim 5 and thus, of Theorem 1. $◀$

As $G$ is an induced subgraph of $G^{\circ }$, the forward implication is immediate. We prove the backward implication by induction on the number $s$ of connected components of $H$. The case $s=1$ was shown by Gartland et al. [17]. Thus, assume that $s>1$ and let $C$ be a connected component of $H$. Let $H^{\prime }=H-C$.

Suppose that $G^{\circ }$ contains $H$ as an induced minor. Fix one induced minor model of $H$ in $G$ and let $𝒳$ be the set of vertices of the model. This means that $G^{\circ }[𝒳]$ has $s$ components, each of which is a cycle, and there is a one-to-one mapping from the components of $G^{\circ }[𝒳]$ and components of $H$, so that each cycle is mapped to a cycle of at most its own length.

Let $𝒴\subseteq 𝒳$ be the vertices of $G^{\circ }$ that form the cycle mapped to $C$; each element of $𝒴$ is a subset of $V(G)$. Let $Y\subseteq V(G)$ be the union of all sets in $𝒴$. Note that $G^{\circ }[𝒴]$ is an induced subgraph of ${(G[Y])}^{\circ }$. Thus, by the inductive assumption, $G[Y]$ contains an induced cycle with at least $|V(C)|$ vertices.

Now let $X\subseteq V(G)$ be the union of sets in $𝒳\setminus 𝒴$. Since $𝒴$ is the vertex set of one component of $G^{\circ }[𝒳]$, there are no edges between $𝒳\setminus 𝒴$ and $𝒴$. Consequently, there are no edges in $G$ between $X$ and $Y$, and thus $G^{\circ }[X\setminus Y]$ is an induced subgraph of ${(G-N[Y])}^{\circ }$.

Since $G^{\circ }[𝒳\setminus 𝒴]$, and thus ${(G-N[Y])}^{\circ }$, contains $H^{\prime }$ as an induced minor, by the inductive assumption we know that $G-N[Y]$ contains $H^{\prime }$ as an induced minor. Combining its model with the model of $C$ in $G[Y]$, we obtain an induced minor model of $H$ in $G$. $◀$

Let $\mathscr{H}$ be a class of graphs. An induced $\mathscr{H}$-packing in a graph $G$ is a set $S\subseteq V(G)$ such that every component of $G[S]$ belongs to $\mathscr{H}$. For example, if $\mathscr{H}=\{K_1\}$, then induced $\mathscr{H}$-packing in $G$ if and only if it is an independent set.

The construction of blob graphs allows us to reduce the problem of finding an induced $\mathscr{H}$-packing of maximum size (or weight) in $G$ to solving the MWIS problem in an appropriate induced subgraph of $G^{\circ }$. This is expressed in the following lemma whose proof is immediate, see e.g., [17, Section 4].

The problem with using Lemma 14 is that $𝒳$ might be very large, so the running time of the algorithm solving MWIS on $(G^{\circ }[𝒳],{𝗐}^{\circ })$ is not bounded by a moderate function of $|V(G)|$.

A class $\mathscr{H}$ of graphs is weakly hyperfinite if for every $\delta >0$ there exists $c_{\delta }\in \mathbb{N}$ such that for any $G\in \mathscr{H}$ there exists a set $S\subseteq |V(G)|$ of size at most $\delta \cdot |V(G)|$ so that every component of $G-S$ has at most $c_{\delta }$ vertices [26, Section 16.2]. The following theorem follows the result of Gartland et al. [17]. Again, we include the proof for completeness.

Without loss of generality assume that $t⩾4$. Let $\delta =\epsilon /2$ and let $c_{\delta }$ be the constant witnessing that $\mathscr{H}$ is weakly hyperfinite. Let $G$ be an $n$-vertex instance instance of the problem. Let

Consider the graph $G^{\circ }[𝒳]$; note that it has $𝒪(n^{c_{\delta }})$ vertices and can be constructed in time polynomial in $n$ as $c_{\delta }$ is a constant. We call the algorithm from Theorem 1 for $G^{\circ }[𝒳]$, weigths ${𝗐}^{\circ }$ defined as in Lemma 14, and precision $\epsilon /2$. It running time is quasipolynomial in $𝒪(n^{c_{\delta }})$ and thus in $n$.