Maximum List $𝒓$-Colorable Induced Subgraphs in $𝒌{𝑷}_{\mathrm{𝟑}}$-Free Graphs

We prove three main algorithmic results for $k{P}_3$-free graphs. The first result, proven in Section 3, concerns Max-Weight List $r$-Colorable Induced Subgraph.

Theorem 3 has several interesting consequences. First, it immediately implies that Odd Cycle Transversal can be solved in polynomial time on $k{P}_3$-free graphs, for every $k\in \mathbb{N}$, thus solving a generalized version of the aforementioned open problem of Agrawal et al. [1]. Our result for Odd Cycle Transversal also complements the polynomial-time algorithms for Feedback Vertex Set and Even Cycle Transversal on $k{P}_3$-free graphs of Paesani et al. [16]. Second, Theorem 3 generalizes the recent result of Chudnovsky et al. [4] that List $r$-Coloring can be solved in polynomial time on $k{P}_3$-free graphs for every $r,k\in \mathbb{N}$. Although partially inspired by their approach, as we explain below, our proof of the more general Theorem 3 has the advantage of being considerably shorter and self-contained.

Theorem 3 also makes considerable progress toward a complete complexity dichotomy for Max-Weight List $r$-Colorable Induced Subgraph and Odd Cycle Transversal on $H$-free graphs. Indeed, paired with the recent result of [10], it completely settles the complexity of Max-Weight List $r$-Colorable Induced Subgraph on $H$-free graphs for $r\ge 5$ (see Theorem 1 and the discussion preceding it):

Moreover, paired with the results of [3, 7, 10] mentioned above, Theorem 3 leaves the case $H=k_4{P}_4+k_3{P}_3+k_2{P}_2+k_1{P}_1$, with $k_4\ge 1$ and $k_4+k_3\ge 2$, as the only remaining open case toward a complete complexity dichotomy for Odd Cycle Transversal on $H$-free graphs.

We then consider the distance-$d$ generalizations of Max-Weight Independent Set and List $r$-Coloring, for $d\ge 6$, and prove the following two results.

Paired with the aforementioned result of Eto et al. [8], Theorem 5 completely settles the computational complexity of Max-Weight Distance-$d$ Independent Set on $k{P}_3$-free graphs, except for the only remaining open case $d=4$.

We now explain our approach toward Theorem 3, which combines ideas from [14, 15] and [4]. It is instructive to first consider the special case of Odd Cycle Transversal (by complementation, Max-Weight $2$-Colorable Induced Subgraph) on $k{P}_2$-free graphs, where a very simple algorithm can be obtained. Indeed, $k{P}_2$-free graphs have polynomially many (inclusion-wise) maximal independent sets, and these can be enumerated in polynomial time. Consequently, a maximum-weight induced bipartite subgraph can be found by exhaustively enumerating all pairs of maximal independent sets [3]. However, it is easily seen that even $P_3$-free graphs (i.e., graphs whose connected components are cliques) do not have polynomially many maximal independent sets. But it turns out that a weaker property is enough for our purposes: Admitting a polynomial family of “well-behaved” vertex sets such that every maximal independent set is contained in one of these sets. In our case, “well-behaved” means inducing a $P_3$-free subgraph. The intuition is that, given such a family, we can efficiently guess the color classes, each of which will be a disjoint union of cliques, and then match vertices to the possible color classes.

The following key notion, which we dub amiable family, was first introduced by Lozin and Mosca [15]. For a graph $G$, a family $𝒮\subseteq 2^{V(G)}$ of subsets of $V(G)$ is an amiable family if it satisfies the following two properties:

• $\mathrm{■}$

  Each member of $𝒮$ induces a $P_3$-free subgraph in $G$;

• $\mathrm{■}$

  Each (inclusion-wise) maximal independent set of $G$ is contained in some member of $𝒮$.

Lozin and Mosca [15] showed that, when $k=2$, every $k{P}_3$-free graph $G$ admits an amiable family of size polynomial in $|V(G)|$ and which can be computed in polynomial time. Later, Lozin [14] observed how such property in fact holds for every $k\ge 2$ (see Lemma 8 for a formal statement). Given an amiable family $𝒮$ of polynomial size of a $k{P}_3$-free graph $G$, we would like to exhaustively solve Max-Weight List $r$-Colorable Induced Subgraph on every possible $r$-tuple consisting of members of $𝒮$. More precisely, let $(S_1,\mathrm{\dots },S_r)\in {𝒮}^r$ be an $r$-tuple of members of $𝒮$. We would like to find a maximum-weight induced subgraph of $G[{\bigcup }_{i\in [r]}{S}_i]$ which admits an $r$-coloring respecting the given $r$-list assignment and such that, for $i=1,\mathrm{\dots },r$, all vertices colored $i$ are contained in $S_i$. To do this, we then extend an idea of Chudnovsky et al. [4] as follows. We reduce our problem to that of finding a maximum-weight matching in an auxiliary bipartite graph where one partition class $Y$ consists of ${\bigcup }_{i\in [r]}{S}_i$, the other class $X$ consists of the connected components of the subgraphs $G[S_i]$, for $i=1,\mathrm{\dots },r$, and there is an edge between $y\in Y$ and $x\in X$ if and only if $y$ belongs to the connected component $x$. Since each weighted matching problem can be solved in polynomial time using the Hungarian method (see, e.g., [17, Theorem 17.3]) and we build ${|𝒮|}^r$ auxiliary problems, which is a polynomial in $|V(G)|$, a solution to Max-Weight List $r$-Colorable Induced Subgraph can be found in polynomial time.

In order to prove Theorems 5 and 6, we consider the following distance-$d$ generalization of the notion of amiable family. For a graph $G$, a family $𝒮\subseteq 2^{V(G)}$ of subsets of $V(G)$ is a distance-$d$ amiable family if it satisfies the following properties:

• $\mathrm{■}$

  Each member of $𝒮$ induces a $P_3$-free subgraph in $G$;

• $\mathrm{■}$

  For each $S\in 𝒮$, the connected components of $G[S]$ are pairwise at distance at least $d$ in $G$;

• $\mathrm{■}$

  Each (inclusion-wise) maximal distance-$d$ independent set of $G$ is contained in some member of $𝒮$.

Clearly, a distance-$2$ amiable family is nothing but an amiable family. Our main technical contribution is the following Lemma 7, proven in Section 4. Although the algorithm for Lemma 7 is inspired by the case $d=2$ and hence by the work of Lozin and Mosca [15], its proof of correctness is much more involved and requires genuinely new ideas.

Equipped with Lemma 7, we immediately obtain Theorem 5. Indeed, in order to solve Max-Weight Distance-$d$ Independent Set on a $k{P}_3$-free graph $G$, we simply find in polynomial time a distance-$d$ amiable family $𝒮$ of $G$ as above and, for each member $S\in 𝒮$, find a max-weight independent set in the $P_3$-free graph $G[S]$. The latter can be clearly done in polynomial time, thus proving Theorem 5. The proof of Theorem 6 is similar to that of Theorem 3, the only difference being the use of a distance-$d$ amiable family for $d\ge 6$, and hence omitted.

A remark about our approach, which combines ideas of Lozin and Mosca [14, 15] and Chudnovsky et al. [4], is in place. The proof of Chudnovsky et al. [4] that List $r$-Coloring ($r\ge 1$) is polynomial-time solvable on $k{P}_3$-free graphs generalizes the earlier result of Hajebi et al. [9] that List $5$-Coloring is polynomial-time solvable on $k{P}_3$-free graphs, by replacing the second step in the proof of Hajebi et al. (see [9, Theorem 4.3]) with a significantly simpler argument (the aforementioned reduction to a bipartite matching problem) that, in addition, works for all $r\in \mathbb{N}$. However, their result still relies on the very technical first step of Hajebi et al. (see [9, Theorem 5.1]). Our approach can be viewed as a step further in the direction of simplifying and generalizing, as exemplified by our Theorems 3 and 6, which extend in different ways the main result of Chudnovsky et al. [4] by means of an arguably elegant and self-contained proof.

Proofs of statements marked with “$\star$” are omitted due to space constraints.

Consider an $r$-tuple $(S_1,\mathrm{\dots },S_r)\in {𝒮}^r$. For every $i\in [r]$, let $c_i$ be the number of connected components of $G[S_i]$ and let $S_i^1,\mathrm{\dots },S_i^{c_i}$ be an arbitrary ordering of the connected components of $G[S_i]$. By definition of distance-$d$ amiable family, each such connected component of $G[S_i]$ is a clique and any two of them are pairwise at distance at least $d$ in $G$.

The first step of our algorithm consists in preprocessing the graph $G[{\bigcup }_{i\in [r]}{S}_i]$ as follows. For every $i\in [r]$, if there exists a vertex $v\in S_i$ such that $i\notin L(v)$, then we remove $v$ from $S_i$, that is, we set $S_i=S_i\setminus \{v\}$. Observe that this preprocessing is safe. Indeed, if $H$ is an induced subgraph of $G[{\bigcup }_{i\in [r]}{S}_i]$ for which there exists a $(d,r)$-coloring $\varphi$ satisfying both 1 and 2, then surely $\varphi (v)\ne i$ if $v\in V(H)$.

We next show that finding such an induced subgraph of $G[{\bigcup }_{i\in [r]}{S}_i]$ of maximum weight boils down to finding a maximum-weight matching in an auxiliary weighted bipartite graph $B$ constructed as follows. The graph $B$ has bipartition $X\cup Y$ and edge set $E(B)$, where

Moreover, for each $v\in {\bigcup }_{i\in [r]}{S}_i$, every edge of $B$ incident to $y_v$ is assigned the weight $w(v)$. Note that $|V(B)|=|{\bigcup }_{i\in [r]}{S}_i|+{\sum }_{i\in [r]}{c}_i\le |V(G)|+r|V(G)|=(r+1)|V(G)|$.

Now, by Claim 10, our problem reduces to finding a maximum-weight matching in the bipartite graph $B$, which can be done in $O({|V(B)|}^3)$-time using the Hungarian method (see [17, Theorem 17.3]). Since $|V(B)|\le (r+1)|V(G)|$, this completes the proof of Lemma 9. $◀$

We can finally sketch the proof of Theorem 3.

Given a $k{P}_3$-free graph $G$ and an $r$-list assignment $L$ of $G$, the following algorithm outputs, in polynomial time, an induced subgraph $H$ of $G$ admitting a coloring that respects $L$ and such that $H$ is of maximum weight among all such subgraphs of $G$.

1. 1.

   Compute an amiable family $𝒮$ of $G$ of size ${|V(G)|}^{O(k)}$.

2. 2.

   For each $r$-tuple $(S_1,\mathrm{\dots },S_r)\in {𝒮}^r$, find a maximum-weight induced subgraph $H$ of $G[{\bigcup }_{i\in [r]}{S}_i]$ which admits a coloring $\varphi :V(H)\to [r]$ satisfying 1 and 2 of Lemma 9.

3. 3.

   Among all induced subgraphs computed in Step $2$, output one of maximum weight.

$◀$

To prove the lemma, we provide, for every $d\ge 6$ and every $k\ge 1$, an algorithm ${\mathrm{\Lambda }}_k^d$ which takes as input a $k{P}_3$-free graph $G$, together with an arbitrary ordering of $V(G)$, and a subset $F\subseteq V(G)$, and outputs an $F$-avoiding distance-$d$ amiable family ${\mathrm{\Lambda }}_k^d(G,F)$ of $G$. The pseudo-code of the algorithm is given in Algorithm 1. Note that, if the input graph $G$ is the empty graph, ${\mathrm{\Lambda }}_k^d$ correctly outputs ${\mathrm{\Lambda }}_k^d(G)=\{\mathrm{\varnothing }\}$.

In the following, we prove three claims (Claims 11, 12, and 13) which altogether show that, for every $d\ge 6$ and every $k\ge 1$, if $G$ is a $k{P}_3$-free graph and $F\subseteq V(G)$, then the family ${\mathrm{\Lambda }}_k^d(G,F)$ is indeed an $F$-avoiding distance-$d$ amiable family. We will then show that ${\mathrm{\Lambda }}_k^d(G,F)$ has size ${|V(G)|}^{O(k)}$ and that the algorithm ${\mathrm{\Lambda }}_k^d$ has running time ${|V(G)|}^{O(k)}$. Taking $F=\mathrm{\varnothing }$, will prove the lemma.

Given a graph $G$ on $n$ vertices and an ordering $v_1,\mathrm{\dots },v_n$ of $V(G)$, we let $G_i=G[\{v_1,\mathrm{\dots },v_i\}]$. Moreover, an induced path in $G$ with vertex set $\{x_1,x_2,\mathrm{\dots },x_{\mathrm{\ell }}\}$ and edge set $\{x_1{x}_2,x_2{x}_3,\mathrm{\dots }{x}_{\mathrm{\ell }-1}{x}_{\mathrm{\ell }}\}$ is denoted by listing its vertices in the natural order $x_1{x}_2\mathrm{\cdots }{x}_{\mathrm{\ell }}$.

For fixed $d\ge 6$, we proceed by induction on $k$. The statement holds for $k=1$, since for every $P_3$-free graph $G$ and every $F\subseteq V(G)$, ${\mathrm{\Lambda }}_1^d(G)=\{V(G)\setminus F\}$. Suppose now that $k>1$ and that the statement holds for $k-1$. Let $G$ be an $n$-vertex $k{P}_3$-free graph and let $F\subseteq V(G)$ as in input. For every $i\in [n]$, let ${𝒮}^i$ be the state of the family $𝒮$ at the end of the $i$-th iteration of the main loop. We show by induction on $i$ that each member of ${𝒮}^i$ induces a $P_3$-free subgraph of $G$ whose connected components are pairwise at distance at least $d$ in $G$. The case $i=1$ trivially holds, since either $v_1\in F$ in which case ${𝒮}^1=\{\mathrm{\varnothing }\}$, or $v_1\notin F$ in which case ${𝒮}^1=\{\{v_1\}\}$. Thus, suppose that $i>1$ and that the statement holds for $i-1$.

Consider $S\in {𝒮}^i$. If $S\in {𝒮}^{i-1}$ then, by the induction hypothesis, $G[S]$ is $P_3$-free and its connected components are pairwise at distance at least $d$ in $G$. Thus, we may assume that $S\notin {𝒮}^{i-1}$. This implies that $S$ is added to ${𝒮}^i$ in one of the three inner loops during the $i$-th iteration of the main loop. If $S$ is added in line 6 as an extension of a member of ${𝒮}^{i-1}$, then the statement holds by construction. Suppose next that $S$ is added to ${𝒮}^i$ in line 10. Hence, there exist an induced $P_3$ $uvw$ in $G_i$ such that $u\notin F$ and a set $C\in {\mathrm{\Lambda }}_{k-1}^d(G[N_G^{\ge 4}(u)],(F\cap N_G^{\ge 4}(u))\cup (N_G^{\ge 4}(u)\cap N_G^{\le d-1}(u)))$ such that $S=C\cup \{u\}$. Observe now that since $G$ is $k{P}_3$-free and $(N_G(v)\cup N_G(w))\cap N_G^{\ge 4}(u)=\mathrm{\varnothing }$, the graph $G[N_G^{\ge 4}(u)]$ is $(k-1)P_3$-free, and thus, by the induction hypothesis on $k-1$, every member of ${\mathrm{\Lambda }}_{k-1}^d(G[N_G^{\ge 4}(u)],(F\cap N_G^{\ge 4}(u))\cup (N_G^{\ge 4}(u)\cap N_G^{\le d-1}(u)))$ induces a $P_3$-free subgraph of $G$ whose connected components are pairwise at distance at least $d$ in $G[N_G^{\ge 4}(u)]$. We claim that then, the connected components of $G[C]$ are in fact pairwise at distance at least $d$ in $G$. Suppose, to the contrary, that there exist two connected components $Q_1$ and $Q_2$ of $G[C]$ such that $d_G(Q_1,Q_2)\le d-1$. Since the distance in $G[N_G^{\ge 4}(u)]$ between $Q_1$ and $Q_2$ is at least $d$, every shortest path in $G$ from $Q_1$ to $Q_2$ contains at least one vertex of $V(G)\setminus N_G^{\ge 4}(u)$; let $P$ be such a shortest path and let $x\in V(G)\setminus N_G^{\ge 4}(u)$ be an arbitrary vertex on $P$. Clearly, $d_G(u,x)\le 3$. Now, by Claim 11, $C\cap ((F\cap N_G^{\ge 4}(u))\cup (N_G^{\ge 4}(u)\cap N_G^{\le d-1}(u)))=\mathrm{\varnothing }$ which implies, in particular, that $C\subseteq N_G^{\ge d}(u)$. It follows that for $j\in [2]$,

Since, by assumption, $d_G(Q_1,Q_2)\le d-1$, we conclude that $2(d-3)\le d-1$, that is, $d\le 5$, a contradiction. Thus, the connected components of $G[C]$ are pairwise at distance at least $d$ in $G$. Since $C\subseteq N_G^{\ge d}(u)$, as previously observed, and $G[C]$ is $P_3$-free, it follows that $S=C\cup \{u\}$ induces a $P_3$-free graph whose connected components are pairwise at distance at least $d$ in $G$. We conclude similarly in the case where $S$ is added to ${𝒮}^i$ in line 14. $\mathrm{⊲}$

For fixed $d\ge 6$, we proceed by induction on $k$. The statement clearly holds for $k=1$, since for every $P_3$-free graph $G$ and every $F\subseteq V(G)$, ${\mathrm{\Lambda }}_1^d(G,F)=\{V(G)\setminus F\}$. Suppose now that $k>1$ and that the statement holds for $k-1$. Let $G$ be a $k{P}_3$-free graph and let $F\subseteq V(G)$ as in input. For every $i\in [n]$, let ${𝒮}^i$ be the state of the family $𝒮$ at the end of the $i$-th iteration of the main loop. Furthermore, given a distance-$d$ independent set $I$ of $G$ such that $I\subseteq V(G_i)$, we say that $I$ is $G_i$-compatible if for every $u\in I$ and every connected component $Q$ of $G_i$ such that $u$ is connected to $Q$ in $G$, there exists a shortest $u,Q$-path $P_{u,Q}$ in $G$ such that $N_G^{\le 2}(u)\cap V(P_{u,Q})\subseteq V(G_i)$. We now show, by induction on $i$, that for every $G_i$-compatible $F$-avoiding distance-$d$ independent set $I$ of $G$ such that $I\subseteq V(G_i)$, there exists $S\in {𝒮}^i$ such that $I\subseteq S$. Note that this is enough to prove our statement for $k$, since any $F$-avoiding distance-$d$ independent set of $G=G_n$ is surely $G_n$-compatible.

The base case $i=1$ trivially holds, since either $v_1\in F$ and ${𝒮}^1=\{\mathrm{\varnothing }\}$ in which case $\mathrm{\varnothing }$ is the only $G_1$-compatible $F$-avoiding distance-$d$ independent of $G_1$, or $v_1\notin F$ and ${𝒮}^1=\{\{v_1\}\}$ in which case $\{v_1\}$ is the only maximal $G_1$-compatible $F$-avoiding distance-$d$ independent set of $G_1$. Thus, suppose that $i>1$ and that the statement holds for $i-1$.

Consider a $G_i$-compatible $F$-avoiding distance-$d$ independent set $I$ of $G$ such that $I\subseteq V(G_i)$. If $I\subseteq V(G_{i-1})$ and $I$ is $G_{i-1}$-compatible then, by the induction hypothesis, there exists $S\in {𝒮}^{i-1}$ such that $I\subseteq S$. Observe now that, by construction, there then exists $S^{\prime }\in {𝒮}^i$ such that $S\subseteq S^{\prime }$ and hence $I\subseteq S^{\prime }$. Thus, assume that this does not hold. This implies that either $I⊈V(G_{i-1})$, or $I\subseteq V(G_{i-1})$ but $I$ is not $G_{i-1}$-compatible. We distinguish these two cases and argue that we can always find $S\in {𝒮}^i$ such that $I\subseteq S$.

$I⊈V(G_{i-1})$.
Hence, $v_i\in I$. Since $I$ is $F$-avoiding, $v_i\notin F$. We claim that $I\setminus \{v_i\}$ is $G_{i-1}$-compatible. Indeed, since $I$ is $G_i$-compatible, for every $u\in I\setminus \{v_i\}$ and every connected component $Q$ of $G_i$ such that $u$ is connected to $Q$ in $G$, there exists a shortest $u,Q$-path $P_{u,Q}$ in $G$ such that $N_G^{\le 2}(u)\cap V(P_{u,Q})\subseteq V(G_i)$. But $v_i$ is at distance at least $d\ge 6$ from $u$ in $G$ and so $v_i\notin (N_G^{\le 2}(u)\cap V(P_{u,Q}))$, that is, $N_G^{\le 2}(u)\cap V(P_{u,Q})\subseteq V(G_{i-1})$ which proves our claim. By the induction hypothesis, there exists $S\in {𝒮}^{i-1}$ such that $I\setminus \{v_i\}\subseteq S$. If $G[S\cup \{v_i\}]$ is $P_3$-free and its connected components are pairwise at distance at least $d$ in $G$, then $S\cup \{v_i\}\in {𝒮}^i$ by construction (cf. line 6) and $I\subseteq S\cup \{v_i\}$. Thus, we may assume that this does not hold. Hence, either $G[S\cup \{v_i\}]$ contains at least one induced $P_3$, or $G[S\cup \{v_i\}]$ is $P_3$-free but at least two of its connected components are at distance strictly less than $d$ in $G$.

$G[S\cup \{v_i\}]$ contains at least one induced $P_3$.
By Claim 12, $G[S]$ is $P_3$-free and thus, any induced $P_3$ in $G[S\cup \{v_i\}]$ must contain $v_i$. We distinguish two cases. Suppose first that there exist a connected component $Q$ of $G[S]$ and a vertex $u\in Q$ such that $v_i$ is adjacent to $u$ but not complete to $Q$, say $w\in Q$ is nonadjacent to $v_i$. Note that at some point during the $i$-th iteration of the main loop, the induced $P_3$ $v_{i}uw$ is considered in the second inner loop, since $v_i\notin F$. Furthermore, since $G$ is $k{P}_3$-free and $(N_G(u)\cup N_G(w))\cap N_G^{\ge 4}(v_i)=\mathrm{\varnothing }$, the graph $G[N_G^{\ge 4}(v_i)]$ is $(k-1)P_3$-free. Thus, by the induction hypothesis on $k-1$ and since $I\setminus \{v_i\}\subseteq N_G^{\ge d}(v_i)\setminus F$, there exists $C\in {\mathrm{\Lambda }}_{k-1}^d(G[N_G^{\ge 4}(v_i)],(F\cap N_G^{\ge 4}(v_i))\cup (N_G^{\ge 4}(v_i)\cap N_G^{\le d-1}(v_i)))$ such that $I\setminus \{v_i\}\subseteq C$. But then, $C\cup \{v_i\}\in {𝒮}^i$ and $I\subseteq C\cup \{v_i\}$. The case where, for every connected component $Q$ of $G[S]$ the vertex $v_i$ is either complete or anticomplete to $Q$, is handled similarly.

$G[S\cup \{v_i\}]$ is $P_3$-free but at least two of its connected components are at distance strictly less than $d$ in $G$.
By Claim 12, the connected components of $G[S]$ are pairwise at distance at least $d$ in $G$ and so there must exist a connected component $Q$ of $G[S\cup \{v_i\}]$ at distance strictly less than $d$ in $G$ to the connected component of $G[S\cup \{v_i\}]$ containing $v_i$. Now, since $v_i$ is connected to $Q$ in $G$ and $v_i\in I$, the assumption that $I$ is $G_i$-compatible implies that there exists a shortest $v_i,Q$-path $P_{v_i,Q}$ in $G$ such that $N_G^{\le 2}(v_i)\cap V(P_{v_i,Q})\subseteq V(G_i)$. Let $u_1,u_2\in V(G_i)$ be the two vertices on $P_{v_i,Q}$ at distance one and two, respectively, from $v_i$. Note that at some point during the $i$-th iteration of the main loop, the induced $P_3$ $v_i{u}_1{u}_2$ is considered in the second inner loop, since $v_i\notin F$. Moreover, since $G$ is $k{P}_3$-free and $(N_G(u_1)\cup N_G(u_2))\cap N_G^{\ge 4}(v_i)=\mathrm{\varnothing }$, the graph $G[N_G^{\ge 4}(v_i)]$ is $(k-1)P_3$-free. Thus, by the induction hypothesis on $k-1$ and since $I\subseteq N_G^{\ge d}(v_i)\setminus F$, there exists $C\in {\mathrm{\Lambda }}_{k-1}^d(G[N_G^{\ge 4}(v_i)],(F\cap N_G^{\ge 4}(v_i))\cup (N_G^{\ge 4}(v_i)\cap N_G^{\le d-1}(v_i)))$ such that $I\setminus \{v_i\}\subseteq C$. But then, $C\cup \{v_i\}\in {𝒮}^i$ and $I\subseteq C\cup \{v_i\}$.

$I\subseteq V(G_{i-1})$ but $I$ is not $G_{i-1}$-compatible.
Hence, there must exist $u\in I$ and a connected component $Q$ of $G_i$ to which $u$ is connected in $G$ such that $v_i\in N_G^{\le 2}(u)\cap V(P_{u,Q})$, where $P_{u,Q}$ is a shortest path in $G$ from $u$ to $Q$ given by the $G_i$-compatibility of $I$. Let $u_1,u_2\in V(G_i)$ be the vertices on $P_{u,Q}$ at distance one and two, respectively, from $u$. Note that at some point during the $i$-th iteration of the main loop, the induced $P_3$ $u{u}_1{u}_2$ is considered in the second inner loop, since $v_i\notin F$. Moreover, since $G$ is $k{P}_3$-free and $(N_G(u_1)\cup N_G(u_2))\cap N_G^{\ge 4}(u)=\mathrm{\varnothing }$, the graph $G[N_G^{\ge 4}(u)]$ is $(k-1)P_3$-free. Thus, by the induction hypothesis on $k-1$ and since $I\subseteq N_G^{\ge d}(u)\setminus F$, there exists $C\in {\mathrm{\Lambda }}_{k-1}^d(G[N_G^{\ge 4}(u)],(F\cap N_G^{\ge 4}(u))\cup (N_G^{\ge 4}(u)\cap N_G^{\le d-1}(u)))$ such that $I\setminus \{u\}\subseteq C$. But then, $C\cup \{u\}\in {𝒮}^i$ and $I\subseteq C\cup \{u\}$.