A Parameterized Study of Secluded Structures in Directed Graphs

We show that the Total-Secluded Strongly Connected Subgraph problem is fixed-parameter tractable when parameterized with $k$. Precisely, we prove the following result:

We design our FPT algorithm for Total-Secluded Strongly Connected Subgraph problem using recursive understanding, a technique introduced by [12] and recently used successfully for various parameterized problems [3, 11, 6, 16]. Specifically, [16] prove a meta-result stating that if a problem is FPT on highly-connected graphs and expressible in Counting Monadic Second-Order Logic, it is also FPT on general graphs. Thereby, this theorem allows to shortcut the analysis and algorithm for the breakable case of recursive understanding. However, it comes at the price of being nonconstructive and not giving a concrete bound on the runtime. For this reason, it is still valuable to apply recursive understanding directly. In future work, it could be promising to apply and generalize this theorem for directed graphs. We visualize the overall structure of the algorithm in Figure 1.

On a high level, recursive understanding algorithms work by first finding a small balanced separator of the underlying undirected graph. If no suitable balanced separator exists, the graph must be highly connected, which makes the problem simpler to solve. In the other case, we reduce and simplify one side of the separator while making sure to keep an equivalent set of solutions in the whole graph. By choosing parameters in the right way, this process reduces one side of the separator enough to invalidate the balance of the separator. Therefore, we have made progress and can iterate with another balanced separator or reach the base case.

In our case, looking for a separator of size at most $k$ makes the framework applicable. Crucially, this is because in any secluded subgraph $G[S]$, where $S\subseteq \mathrm{V}(G)$, the neighborhood $\mathrm{N}(S)$ acts as a separator between $S$ and $\mathrm{V}(G)\setminus \mathrm{N}[S]$. Therefore, if no balanced separator of size at most $k$ exists, we can deduce that either $S$ itself or $\mathrm{V}(G)\setminus S$ must have a small size. This observation makes the problem significantly easier to solve in this case, using the color coding technique developed in [3].

In the other case, we can separate our graph into two balanced parts, $U$ and $W$, with a separator $P$ of size $\left|P\right|\le k$. Now, our goal is to solve the same problem recursively for one of the sides, say $W$ and replace that side with an equivalent graph of bounded size that only contains all necessary solutions. However, finding subsets of solutions is not the same as finding solutions; the solution $S$ for the whole graph could heavily depend on including some vertices in $U$. That being said, the different options for this influence are limited. At most $2^k$ different subsets $X$ of $P$ could be part of the solution. For any such $X$, the solution can only interact across $P$ in a limited number of ways. For finding strongly connected subgraphs, we have to consider for which pair $(x_1,x_2)\in X\times X$ there already is a $x_1$-$x_2$-path in the $U$-part of the complete solution $S$. This allows us to construct a new instance for every such possibility by encoding $X$ and the existing paths into $W$. These instances are called boundary complementations. We visualize the idea of this construction in Figure 2.

Fundamentally, we prove that an optimal solution for the original graph exists, that coincides in $W$ with an optimal solution to the boundary complementation graph in which $U$ is replaced. Hence, we restrict the space of solutions to only those whose neighborhood in $W$ coincides with the neighborhood of an optimal solution to some boundary complementation. The restricted instance consists of a bounded-size set $B$ of vertices that could be part of $\mathrm{N}(S)$ and components in $W\setminus B$ that can only be included in $S$ completely or not at all. We introduce graph extensions to formalize when exactly these components play the same role in a strongly connected subgraph. Equivalent extensions can then be merged and compressed into equivalent extensions of bounded size. In total, this guarantees that $W$ is shrunk enough to invalidate the previous balanced separator, and we can restart the process.

For any family of graphs $ℱ$, a graph $G$ is called $ℱ$-Free if it does not contain any graph in $ℱ$ as an induced subgraph. Depending on the context both $ℱ$ and $G$ are either both undirected or both directed. The widely-studied Secluded $ℱ$-Free Subgraph problem on undirected graphs is FPT (with parameter $k$) using recursive understanding [11] or branching on important separators [15] when we restrict it to connected solutions. We study the directed version of the problem and surprisingly, it turns out to be W[1]-hard for almost all forbidden graph families $ℱ$ even with respect to the parameter $k+w$. Precisely, we prove the following theorem.

We establish an almost complete dichotomy that highlights the few cases of families $ℱ$ for which the problem remains tractable. One of these exceptions is if $ℱ$ contains an edgeless graph of any size, where we employ our algorithm for Out-Secluded $\alpha$-Bounded Subgraph. Theorem 2 also implies the following result for the directed variant of Secluded Tree problem.

In the undirected setting, the Secluded Clique problem is natural and has been studied specifically. There is an FPT-algorithm running in time $2^{𝒪(k\log k)}{n}^{𝒪(1)}$ through contracting twins [11]. The previous best algorithm however uses the general result for finding secluded $ℱ$-free subgraphs in time $2^{𝒪(k)}{n}^{𝒪(1)}$ [15]. By using important separators, they require time at least $4^k{n}^{𝒪(1)}$. This property is naturally generalizable to directed graphs via tournament graphs. We go one step further.

The independence number of an undirected or directed graph $G$ is the size of the maximum independent set in $G$ (or its underlying undirected graph). If $G$ has independence number at most $\alpha$, we also call it $\alpha$-bounded. This concept has been used to leverage parameterized results from the simpler tournament graphs to the larger graph class of $\alpha$-bounded graphs [20, 10, 18]. We prove the following results:

We achieve the goal via a branching algorithm, solving Secluded $\alpha$-Bounded Subgraph for all neighborhood definitions in FPT time (Theorems 4 and 5). Our algorithm initially picks a vertex subset $U\subseteq \mathrm{V}(G)$ and looks only for solutions in the two-hop neighborhood of $U$. A structural property of $\alpha$-bounded graphs guarantees that any optimal solution is found in this way. On a high level, the remaining algorithm depends on two branching strategies. First, we branch on forbidden structures in the two-hop neighborhood of $U$, to ensure that it becomes $\alpha$-bounded. Second, we branch on farther away vertices to reach a secluded set.

Note that Theorem 5 is inherently also an undirected result. Furthermore, the ideas behind the algorithm can in turn be used for the simpler undirected Secluded Clique problem. By a closer analysis of these two high-level rules, we arrive at a branching vector of $(1,2)$ for Secluded Clique. This results in the following runtime, a drastic improvement on the previous barrier of $4^k{n}^{𝒪(1)}$.

We consider Total-Secluded Strongly Connected Subgraph and prove Theorem 1 in Section 2. The hardness result about Out-Secluded $ℱ$ Weakly Connected Subgraph in Theorem 2 is proved in Section 3. In Section 4, we give the algorithm for Out-Secluded $\alpha$-Bounded Subgraph and prove Theorem 4. Due to space constraints, the algorithms and proofs of Theorems 5 and 6 can be found in the full version [21]. Proofs of statements marked with ($\star$) are also deferred to the full version.

Let $G$ be a directed graph. For a vertex $v\in \mathrm{V}(G)$, we denote the out-neighborhood by ${\mathrm{N}}^{+}(v)=\left\{u\right|(v,u)\in \mathrm{E}(G)\}$ and the in-neighborhood by ${\mathrm{N}}^{-}(v)=\left\{u\right|(u,v)\in \mathrm{E}(G)\}$. The total-neighborhood is defined as $\mathrm{N}(v)={\mathrm{N}}^{+}(v)\cup {\mathrm{N}}^{-}(v)$. We use the same notation for sets of vertices $S\subseteq \mathrm{V}(G)$ as ${\mathrm{N}}^{+}(S)={\bigcup }_{v\in S}{\mathrm{N}}^{+}(v)\setminus S$. Furthermore, for all definitions, we also consider their closed version that includes the vertex or vertex set itself, denoted by ${\mathrm{N}}^{+}[v]={\mathrm{N}}^{+}(v)\cup \left\{v\right\}$. For a vertex set $S\subseteq \mathrm{V}(G)$, we write $G[S]$ for the subgraph induced by $S$ or $G-S$ for the subgraph induced by $\mathrm{V}(G)\setminus S$. We also use $G-v$ instead of $G-\left\{v\right\}$.

When we refer to a component of a directed graph, we mean a component of the underlying undirected graph, that is, a maximal set that induces a weakly connected subgraph. In contrast, a strongly connected component refers to a maximal set that induces a strongly connected subgraph. For standard parameterized definitions, we refer to [5].

We construct a $v_1$-$v_2$-path for all $v_1,v_2\in U\cup \mathrm{V}(D_2)$ that only uses edges in $\mathrm{E}(D_2)$, $E_{G{D}_2}$, and $G[U]$ by case distinction.

Paths $U\to U$.

Let $u_1,u_2\in U$. If there is a path from $u_1$ to $u_2$ in $G[U]$, this path also exists after exchanging $(D_1,E_{G{D}_1})$ to $(D_2,E_{G{D}_2})$. If the path passes through $D_1$, since $𝒞(D_1,E_{G{D}_1})=𝒞(D_2,E_{G{D}_2})$, we can exchange all subpaths through $D_1$ by subpaths through $D_2$.

Paths $\mathrm{V}(D_2)\to U$.

Let $v\in \mathrm{V}(D_2),u\in U$. We construct a $v$-$u$-path by first walking from $v$ to any sink component $T$ in $\text{SCC}(D_2)$. If there is no edge $(t,u^{\prime })\in E_{G{D}_2}$ with $t\in T,u^{\prime }\in U$ that we can append, since $𝒯(D_1,(D_1,E_{G{D}_1}))=𝒯(D_2,(D_2,E_{G{D}_2}))$, there must also be a sink component in $\text{SCC}(D_1)$ with no outgoing edge to $U$. However, this is a contradiction to the fact that ${\text{Ext}}_{G[U]}(D_1,E_{G[U]D_1})$ is strongly connected with nonempty $U$. Therefore, we can find a $(t,u^{\prime })$ to append for some $t\in T,u^{\prime }\in U$. From $u^{\prime }$, there is already a path to $u$, as proven in the first case.

Paths $U\to \mathrm{V}(D_2)$.

Next, we construct a $u$-$v$-path backwards by walking from $v$ backwards to a source $s$ in $D_2$. Analogously, there is an edge $(u^{\prime },s)\in E_{G{D}_2}$ for some $u^{\prime }\in U$ since $𝒮(D_1,E_{G{D}_1})=𝒮(D_2,E_{G{D}_2})$, which we append. From $u$, there is a path to $u^{\prime }$, as proven in the first case, which we prepend to the rest of the path.

Paths $\mathrm{V}(D_2)\to \mathrm{V}(D_2)$.

Let $v_1,v_2\in \mathrm{V}(D_2)$. To construct a $v_1$-$v_2$-path, we can just walk from $v_1$ to any $u\in U$ and from there to $v_2$ as shown before.

$◀$

Furthermore, observe that the union of two extensions creates another extension where source, sink and connection sets correspond exactly to the union of the previous sets. Hence, the union of two equivalent extensions will again be equivalent. This fact is formalized in the next observation and will turn out useful in later reduction rules.

Now, we finally define our compression routine, which compresses an extension to a bounded size equivalent extension. If an extension is strongly connected, it is easy to convince yourself that it is always possible to compress the extension to a single vertex. Otherwise, we add one source vertex per neighborhood set in $𝒮(D,E_{GD})$ as well as one sink vertex per neighborhood set in $𝒯(D,E_{GD})$, realizing the same $𝒮$ and $𝒯$. Then, we add vertices in between suitable source and sink vertices to realize exactly the same connections in $𝒞$ without creating additional ones. The result of a compression is visualized in Figure 3. Now, we describe the procedure formally.

Let $G$ be a directed graph with an extension $(D,E_{GD})$. Our compression routine returns an extension that we call compressed extension, denoted as ${\text{Comp}}_G(D,E_{GD})$.

• $\mathrm{■}$

  If $D$ is strongly connected, we contract $D$ to one vertex $v$ and remove self-loops and multiple edges. We adjust $E_{GD}$ by using $v$ instead of $\mathrm{V}(D)$ and removing multiple edges.

• $\mathrm{■}$

  Otherwise, ${\text{Comp}}_G(D,E_{GD})≔(D^{\prime },E_{G{D}^{\prime }})$, where $(D^{\prime },E_{G{D}^{\prime }})$ is an extension such that

  	$\mathrm{V}(D^{\prime })≔$	$\left\{v_S\right|S\in 𝒮(D,E_{GD})\}\cup \left\{v_T\right|T\in 𝒯(D,E_{GD})\}\cup \left\{v_c\right|c\in 𝒞(D,E_{GD})\},$
  	$E_{G{D}^{\prime }}≔$	$\left\{(s,v_S)\right|S\in 𝒮(D,E_{GD}),s\in S\}\cup \left\{(v_T,t)\right|T\in 𝒯(D,E_{GD}),t\in T\}$
  	$\cup$	$\left\{(a,v_c),(v_c,b)\right|c=(a,b)\in 𝒞(D,E_{GD})\}.$

  To define $\mathrm{E}(D)$, consider every source component $C_s$ and sink component $C_t$ in $\text{SCC}(D)$ such that $C_t$ is reachable from $C_s$ in $D$. Let $S≔{\mathrm{N}}_{E_{GD}}^{-}(C_s)$ and $T≔{\mathrm{N}}_{E_{GD}}^{-}(C_t)$ be the corresponding sets in $𝒮(D,E_{GD})$ and $𝒯(D,E_{GD})$.

  • –

    Add the edge $(v_S,v_T)$ to $\mathrm{E}(D)$.

  • –

    For every $c=(a,b)\in 𝒞(D,E_{GD})$ that satisfies $(s,b)\in 𝒞(D,E_{GD})$ and $(a,t)\in 𝒞(D,E_{GD})$ for every $s\in S,t\in T$, add the edges $(v_S,v_c)$ and $(v_c,v_T)$ to $\mathrm{E}(D)$.

Now we go on to prove the properties that are maintained while compressing. Then, we bound the size of a compressed extension and thus also the number of equivalence classes.

For the first property, assume that $D$ is weakly connected. We know by definition that every sink in $D^{\prime }$ is reached by at least one source. Consider a $v_c$ with $c=(a,b)\in 𝒞(D,E_{GD})$. To show that $v_c$ is connected to some $v_S$ and $v_T$, consider the path from $d_1$ to $d_2$ in $D$ that realizes this connection. There must be a source component $C_S$ and a sink component $C_T$ in $\text{SCC}(D)$ such that $d_1$ is reachable from $C_S$ and $C_T$ is reachable from $d_2$. Therefore, any vertex in $C_S$ can also reach $d_2$ and $d_1$ can reach every vertex in $C_T$. By definition of compression, these two components ensure that $v_c$ is connected.

It remains to show that any source is reachable by any other source in the underlying undirected graph. Let $v_S,v_{S^{\prime }}$ be two sources in $D^{\prime }$ with corresponding source components $C$, $C^{\prime }$ in $\text{SCC}(D)$. Since $D$ is weakly connected, there is a path from $C$ to $C^{\prime }$ in the underlying undirected graph. Whenever the undirected path uses an edge in a different direction than the one before, we extend the path to first keep using edges in the same direction until a source or sink component is reached and then go back to the switching point. This new path can directly be transferred to $D^{\prime }$, where we only keep the vertices corresponding to source and sink components. By definition, this is still a path in $D^{\prime }$ that connects $v_S$ to $v_{S^{\prime }}$, and $D^{\prime }$ is weakly connected

The second property is simple to verify, since strongly connected graphs are by definition compressed to single vertices. If $D$ is not strongly connected, $D^{\prime }$ will have at least one source and one sink that are not the same.

Regarding the equivalence, we create one source for every $S\in 𝒮(D,E_{GD})$ with the same set of incoming neighbors and create no other sources. Therefore, $𝒮(D^{\prime },E_{G{D}^{\prime }})=𝒮(D,E_{GD})$ and $𝒯(D^{\prime },E_{G{D}^{\prime }})=𝒯(D,E_{GD})$ follows analogously. For every connection $c\in 𝒞(D,E_{GD})$, we create $v_c$ in $D^{\prime }$ that realizes this connection. Therefore, we know that $𝒞(D^{\prime },E_{G{D}^{\prime }})\supseteq 𝒞(D,E_{GD})$. Since $v_c$ is only reachable from sources and reaches only sinks that do not give new connections, we arrive at $𝒞(D^{\prime },E_{G{D}^{\prime }})=𝒞(D,E_{GD})$. $◀$

We also bound the number of possible different compression outputs as well as their size.

In the past section, we have defined graph extensions and an equivalence relation on them that captures the role they can play in forming strongly connected subgraphs. We have presented a way to compress an extension such that its size only depends on the size of $G$, while remaining equivalent. In the next section, we will use this theory to design reduction rules for Boundaried Max TSSCS. Crucially, we view components outside of the set $B$ as extensions, which allows us to keep only one compressed extension of each equivalence class.

By the previous reduction rules, components of $G-B$ can only be included as a whole or not at all. Notice that since $𝒞(Q_1,E_{B{Q}_1})=𝒞(Q_2,E_{B{Q}_2})$ and Reduction Rule 20, we get $\mathrm{N}(Q_1)=\mathrm{N}(Q_2)$. Let $S$ be a solution to the old instance. We differentiate some cases.

If $S\cap (Q_1\cup Q_2)=\mathrm{\varnothing }$, we know that also $\mathrm{N}(S)\cap (Q_1\cup Q_2)=\mathrm{\varnothing }$. Therefore, the neighborhood size and strong connectivity of $S$ do not change in the new instance, and it is also a solution. If $S$ includes only one of $Q_1$ and $Q_2$, assume without loss of generality $S\cap (Q_1\cup Q_2)=Q_1$, since $Q_1$ is not strongly connected by itself, the solution must include vertices of $B$. Because $\mathrm{N}(Q_1)=\mathrm{N}(Q_2)$, the solution must also include $Q_2$, a contradiction. If $S$ includes both $Q_1$ and $Q_2$, we claim that $S^{\prime }≔S\setminus Q_2$ is a solution for the new instance. The neighborhood size and weight clearly remain unchanged. Strong connectivity follows by Observation 16 and Lemma 15. The last two cases also show that if a solution had to include at least one of $Q_1$ and $Q_2$, that is, $(Q_1\cup Q_2)\cap I\ne \mathrm{\varnothing }$, any solution for the reduced instance must also include $Q_1$. Therefore, the adaptation to $I$ is correct.

Let $S$ be a solution to the reduced instance. Again, if $S$ does not include vertices from $Q_1$, then $S$ will immediately be a solution to the old instance. If $Q_1\subseteq S$, then $S^{\prime }≔S\cup Q_2$ will be a solution to the old instance by Observation 16 and Lemma 15. $◀$

For strongly connected components, the rule is different, since we have to acknowledge the fact that they can be a solution by themselves. For every such component we destroy strong connectivity of smaller-weight equivalent component, which can then be reduced by Reduction Rule 22.

Let $S$ be a solution of the old instance. If $S\cap (Q_1\cup Q_2)=\mathrm{\varnothing }$, then $S$ is also a solution for the new instance. If $S$ includes only one of $Q_1$ and $Q_2$, then we must have $S\in \{Q_1,Q_2\}$, so $S^{\prime }≔Q_1$ is a solution for the new instance with $\omega (S^{\prime })\ge \omega (S)$. If $S$ includes both $Q_1$ and $Q_2$, adding $q_2^{\prime }$ to $S$ obviously gives a solution of the same weight.

For a solution of the reduced instance $S$, we can simply remove $q_2^{\prime }$ if it is inside for a solution to the old instance. $◀$

Using both Reduction Rules 22 and 23 exhaustively makes sure that there are at most two components per extension equivalence class left. The last rule compresses the remaining components to equivalent components of bounded size.

Since $Q$ is not strongly connected, it can only be part of a solution that includes some vertices from $G-Q$. Thus, we can apply Lemmas 15 and 17, and the old instance and the new instance have exactly the same strongly connected subgraphs. Because of $𝒞(Q,E_{BQ})=𝒞(Q^{\prime },E_{B{Q}^{\prime }})$ and Reduction Rule 20, we get $\mathrm{N}(Q)=\mathrm{N}(Q^{\prime })$. Since $\omega (Q^{\prime })=\omega (Q)$, the rule is safe. $◀$

This finally allows us to bound the size of $G-B$. In the next lemma, we summarize the progress of our reduction rules and apply the bounds from the previous section. Note that we need the stronger bound using the neighborhood of the components instead of simply $B$.

Now, we have all that it takes to solve our intermediate problem. The main idea of the algorithm is to shrink $B$ to a bounded size, by solving the problem recursively. Once $B$ is bounded, we apply our reduction rules by viewing components of $G-B$ as extensions, removing redundant equivalent extensions and compressing them. Thereby, we also bound the size and number of components of $G-B$ in terms of $\left|B\right|$ using Lemma 25. By choosing suitable constants, we can show that this decreases the total size of $G$, which will make progress to finally reduce it to the unbreakable case.

Let $ℐ=(G,I,O,B,\omega ,k,T)$ be our Boundaried Max TSSCS instance. See Algorithm 1 for a more compact description of the algorithm. A high level display of the approach can be found in Figure 1. Define $q=2^{2^{2^{c{k}^2}}}$ for a constant $c$. We later show that a suitable $c$ must exist.

First, we run the algorithm from Lemma 26 on the underlying undirected graph of $G$ with $q$ and $k$. If it is $((2q+1)q{2}^k,k)$-unbreakable, we solve the instance directly using the algorithm from Theorem 12.

Therefore, assume that we have a $(q,k)$-separation $(U,W)$. Without loss of generality, since $\left|T\right|\le 2k$ we can assume that $\left|T\cap W\setminus U\right|\le k$. Thus, we can construct a new instance to solve the easier side of the separation. Take $\tilde{G}=G[W],\tilde{I}=I\cap W,\tilde{O}=O\cap W,\tilde{B}=B\cap W$, write $\tilde{\omega }$ for the restriction of $\omega$ to $W$, and set $\tilde{T}=(T\cap W)\cup (U\cap W)$. Since $\left|U\cap W\right|\le k$, also $\left|\tilde{T}\right|\le 2k$ holds and $\tilde{I}≔(\tilde{G},\tilde{I},\tilde{O},\tilde{B},\tilde{\omega },k,\tilde{T})$ is a valid instance, which we solve recursively.

Let $ℛ$ be the set of solutions found in the recursive call. For $R\in ℛ$, define $N_R=\mathrm{N}(R)\cap W$. Define $𝒩=\tilde{T}\cup {\bigcup }_{R\in ℛ}{N}_R$.

We now restrict $B$ in $W$ to use only vertices in the neighborhood that have been neighbors in a solution in $ℛ$, that is, only vertices in $𝒩$. Define $\widehat{B}=(B\cap U)\cup (B\cap 𝒩)$. We now replace $B$ in our instance with $\widehat{B}$ and apply all our reduction rules exhaustively to arrive at the instance $(G^{\ast },I^{\ast },O^{\ast },{\widehat{B}}^{\ast },{\omega }^{\ast },k^{\ast },T^{\ast })$. Finally, we also solve this instance recursively and return the solutions after undoing the reduction rules.

We already proved that the reduction rules and the algorithm for the unbreakable case are correct. The main statement we have to show is that we can replace $B$ with $\widehat{B}$ without throwing away important solutions. That means that the instances $(G,I,O,B,\omega ,k,T)$ and $\widehat{ℐ}≔(G,I,O,\widehat{B},\omega ,k,T)$ are equivalent in the sense that any solution set for one instance can be transformed to a solution set to the other instance with at least the same weights. This justifies solving $\widehat{ℐ}$ instead of $ℐ$. Consider the boundary complementation ${ℐ}^{\prime }≔(G^{\prime },I^{\prime },O^{\prime },B^{\prime },{\omega }^{\prime },k^{\prime })$ and ${\widehat{ℐ}}^{\prime }≔(G^{\prime },I^{\prime },O^{\prime },{\widehat{B}}^{\prime },{\omega }^{\prime },k^{\prime })$ that are caused by the same $(X,Y,Z,R)$. To show the claim, we consider the two directions. Any solution for ${\widehat{ℐ}}^{\prime }$ is immediately a solution for the same boundary complementation for ${ℐ}^{\prime }$ since the only difference is that we limit the possible neighborhood to a subset of $B$.

For the other direction, consider a solution $S$ to ${ℐ}^{\prime }$, and we want to show that there is a solution $\widehat{S}$ to ${\widehat{ℐ}}^{\prime }$ using only vertices of ${\widehat{B}}^{\prime }$ in the neighborhood with $\omega (\widehat{S})\ge \omega (S)$. If $S\cap W=\mathrm{\varnothing }$, then $S$ is also immediately a solution for ${\widehat{ℐ}}^{\prime }$. Therefore, assume $S\cap W\ne \mathrm{\varnothing }$. Define $\tilde{X}≔\tilde{T}\cap S$, $\tilde{Y}≔\tilde{T}\cap {\mathrm{N}}_{G-(W\setminus U)}(S)$, and $\tilde{Z}≔\tilde{T}\setminus (\tilde{X}\cup \tilde{Y})$. Let $\tilde{R}$ be the set of $(a,b)\in \tilde{X}\times \tilde{X}$ such that there is an $a$-$b$-path in $G[S\setminus W\setminus U]$. Finally, let $\tilde{k}≔\left|\mathrm{N}(S)\cap W\right|$. Thus, we can construct a boundary complementation instance $({\tilde{G}}^{\prime },{\tilde{I}}^{\prime },{\tilde{O}}^{\prime },{\tilde{B}}^{\prime },{\tilde{w}}^{\prime },\tilde{k})$ from $(\tilde{X},\tilde{Y},\tilde{Z},\tilde{R})$. One can easily verify that $(S\cap \mathrm{V}({\tilde{G}}^{\prime }))\cup \left\{u_r\right|r\in \tilde{R}\}$ is a feasible solution to this instance. Furthermore, the maximum solution $\tilde{S}\in ℛ$ to this instance gives a new set $\widehat{S}≔(\tilde{S}\cap W)\cup (S\cap U)\subseteq \mathrm{V}(G^{\prime })$ that has at least the same weight as $S$. We also know that $\mathrm{N}(\widehat{S})\subseteq {\widehat{B}}^{\prime }$ and $\left|\mathrm{N}(\widehat{S})\right|\le k$. See Figure 2 for a visualization of the construction corresponding to a solution $S$.

All that remains is to verify that $\widehat{S}$ is strongly connected. For $v_1,v_2\in \tilde{S}\cap W$, we can simply use the $v_1$-$v_2$-path in $\tilde{S}$, replacing subpaths via $u_r$ for $r\in \tilde{R}$ with the actual paths in $S\cap U$. If $v_1\in \tilde{S}\cap W$ and $v_2\in S\cap U$, we can walk to any $x\in \tilde{X}$ which must have a path to $v_2$ in $S$, in which may need to replace subpaths via $W$. This can be done, since $\tilde{S}\cap W$ connects all pairs of $x_1,x_2\in X$ that are not connected via $S\cap U$. The two remaining cases follow by symmetry, justifying the replacement of $B$ with $\widehat{B}$.

Finally, we have to show that the recursion terminates for the right choice of $c$; that is, both recursively solved instances have strictly smaller sizes than the original graph. For the first recursive call, note that the boundary complementation adds at most $k^2\le q$ vertices to $\tilde{G}$. Since $\left|U\setminus W\right|>q$, we have .

For the second recursive call, since $\left|\tilde{T}\right|\le 2k$ and by Lemma 9, we have $\left|𝒩\right|\le 2k+(k+1)k{2}^{c_1{k}^2}\le 2^{c_2{k}^2}$ for constants $c_1$ and $c_2$. After applying all our reduction rules, by Lemma 25 for a suitable choice of $c_3$ and $c$ we get

Since before the reductions, we had $\left|W\setminus U\right|>q$, the reduced graph $G^{\ast }$ also has fewer vertices than $G$. Therefore, this recursive call also makes progress and the recursion terminates.

We follow the analysis of [3]. With Lemma 26, we can test if the undirected version of $G$ is unbreakable in time $2^{k\log q+k}{n}^{𝒪(1)}\le 2^{2^{2^{𝒪(k^2)}}}{n}^{𝒪(1)}$. If the graph turns out to be unbreakable, the algorithm of Theorem 12 solves it in time $2^{𝒪(k^2\log q)}\le 2^{2^{2^{𝒪(k^2)}}}{n}^{𝒪(1)}$. Executing the reduction rules takes polynomial time in $n$ by Lemma 25.

All that is left to do is analyze the recursion. Let $n^{\prime }≔\left|W\right|$. By the separation property, we know that . From the correctness section, we get $\left|\mathrm{V}(G^{\ast })\right|\le \left|\mathrm{V}(G)\right|-n^{\prime }+q$. Note that the recursion stops when the original graph is $(q,k)$-unbreakable, which must be the case if $\left|\mathrm{V}(G)\right|\le 2q$. We arrive at the recurrence