Plane Strong Connectivity Augmentation

Consider an instance $(D,k)$, with $D$ acyclic, and assume that it admits a solution $X$ of size at most $k$. To reconfigure $X$ into a supported solution, we iterate over all faces $F$, and reconfigure $X_F$ in $X$ into a supported completion, while maintaining that $X$ is a solution. Inside each face $F$, we successively consider any subwalk $P$ from a local source $s$ to a consecutive local sink $t$ (recall $P$ is then a directed path). We will show how to reconfigure the endpoints of the restriction $X_P$ belonging to $P$, and only those, to be incident only to $s$ and $t$. It suffices to show this last step, which iterated as above for each pair of consecutive local terminals, and each face, will achieve to reconfigure $X$ into a supported solution. In the following, let us consider such a $P$ between $s$ and $t$, and show the reconfiguration of $X_P$.

We first consider the case where $X_P$ contains an arc with both endpoints on $P$. We modify the endpoints of $X_P$ on $P$ as follows. Remove all arcs with both endpoints on $P$ and replace them with (a single) $(t,s)$. Then for all other arcs of $X_P$, substitute all their endpoints in $P$ with $s$. It is easy to see that these arcs can be modified while preserving a plane embedding for $D+X$. The addition of $(t,s)$ ensures that $V(P)$ is now strongly connected in $D+X$. Then, consider any arc $(x,p)$ in the initial $X_P$, with $p\in P$ and $x\notin P$. Since its modification yields $(x,s)$, note that the path from $x$ to $p$ is preserved after the reconfiguration. Indeed, we may follow $(x,s)$ then any path towards $p$ in $V(P)$. This yields that $D+X$ is still strongly connected, and concludes the proof for this case.

In the remainder of the proof, we may assume all arcs in $X_P$ have exactly one endpoint in $P$. Take $v\in V(P)\setminus \{s,t\}$ to be any vertex incident to arcs of $X_P$ and let $X_v\subseteq X_P$ be the subset of those arcs. Informally, our strategy consists in showing that we can always “shift” their $v$ endpoint “towards” either $s$ or $t$. Consider $v$, and let $u$ (resp. $w$) be the previous (resp. next) vertex incident to $X_P$ when following $P$. When this is not defined, we let $u=s$ (resp. $w=t$). We define $X_u$ (resp. $X_w$) to be the subset of arcs obtained from $X_v$ by substituting every $v$ endpoint of arcs in $X_v$ with $u$ (resp. with $w$), see Figure 2. We will show that $X_v$ can be replaced with either $X_u$ or $X_w$ in $X$ while maintaining a solution. Observe first that by definition of $u,w$, and since the only endpoint of $X_v$ on $P$ is $v$, both $D+X-X_v+X_u$ and $D+X-X_v+X_w$ are plane. Therefore, letting $D^{\prime }=D+X-X_v$, it suffices to show that either $D^{\prime }+X_u$ or $D^{\prime }+X_w$ is strongly connected.

First, observe that $X_v$ forms an oriented star incident to all terminal components of $D^{\prime }$. In $D^{\prime }$, let $Y_v^{\prime }$ be the strong component of containing $v$, ${(S_i^{\prime })}_i$ be the remaining source components, and ${(T_j^{\prime })}_j$ be the remaining sink components. Since $D^{\prime }+X_v$ is strong, $X_v$ contains an arc from $v$ to every $S_i^{\prime }$, and from every $T_j^{\prime }$ to $v$. In particular, we have the following property:

It is easy to see that any plane completion of $D^{\prime }$ satisfying Equation 1 (in place of $X_v$) is also a solution to $D^{\prime }$. We show that either $X_u$ or $X_w$ must satisfy Equation 1. By definition, both $X_u$ and $X_w$ form stars which induce a directed path of length two from every $T_j^{\prime }$ to every $S_i^{\prime }$. In particular, if $Y_v^{\prime }$ is not a terminal component, all terminal components of $D^{\prime }$ are of the form ${(S_i^{\prime })}_i$ or ${(T_j^{\prime })}_j$, meaning both $X_u$ and $X_w$ satisfy Equation 1. We then update $X$ to $X-X_v+X_u$, which maintains a solution for $D$. Now, if $Y_v^{\prime }$ is a source component of $D^{\prime }$, the existence of the directed subpath $(s,\mathrm{\dots },u\mathrm{\dots },v)$ of $P$ implies $u\in Y_v^{\prime }$ as well. Then, $X_u$ contains arcs from all sinks of $D^{\prime }$, ${(T_j^{\prime })}_j$, to $Y_v^{\prime }$, so $X_u$ satisfies Equation 1, so updating $X$ to $X-X_v+X_u$ maintains a solution for $D$. See Figure 2 for an illustration of this case. Symmetrically, when $Y_v^{\prime }$ is a sink component, the subpath $(v,\mathrm{\dots },w,\mathrm{\dots }t)$ yields that $w\in Y_v^{\prime }$, and updating $X$ to $X-X_v+X_w$ yields a solution for $D$.

As long as there exist endpoints of $X_P$ not incident to $s$ or $t$, we reiterate the operation described in the last paragraph. This process terminates, because the number of endpoints of $X_P$ on $P$ other than $s$ or $t$ strictly decreases. Eventually, all endpoints of $X_P$ on $P$ (and only those) will have been reconfigured to either $s$ or $t$, while maintaining that $X$ is a solution. This achieves to show the reconfiguration of $X_P$, and therefore concludes the proof. $◀$

Let $F$ be a face of $D$, and let $\mathrm{𝗅𝗍}=\mathrm{𝗅𝗍}(F)$. Note that the embedding of any supported completion $X$ of $F$ is fully determined by the local terminals (labelled vertices of $F$) to which it is incident. Therefore, our goal is to enumerate all possible labelled outerplanar digraphs between the local terminals. For our purposes, we may consider local terminals as distinct vertices on a cyclic face, up to contracting them afterwards. Each digraph we enumerate can thus be seen as a labelled directed triangulation on $\mathrm{𝗅𝗍}$ vertices. It is well known that the number of labelled triangulations of a polygon with $\mathrm{𝗅𝗍}$ angles corresponds to the Catalan number $C_{\mathrm{𝗅𝗍}-2},$ which is $2^{O(\mathrm{𝗅𝗍})}$, see Walkup [30]. These triangulations can also be enumerated in $2^{O(\mathrm{𝗅𝗍})}$ time using the algorithm of Bespamyatnikh [3]. Then, each triangulation contains $2\mathrm{𝗅𝗍}-3$ edges, and the number of ways to choose either a non-arc, an arc (in either direction) or a digon is bounded by $4^{2\mathrm{𝗅𝗍}-3}=2^{O(\mathrm{𝗅𝗍})}$. Combining the above, the number of labelled outerplanar digraphs, thus of supported completions of $F$, is bounded by $2^{O(\mathrm{𝗅𝗍})}$, and their enumeration takes $2^{O(\mathrm{𝗅𝗍})}$-time. $◀$

The following bounds the number of local terminals across all alternating faces, thus by Lemma 7 the number of their supported completions.

The proof of Lemma 8 is delayed to the appendix of the full version [4], but is easily derived from results by Guattery and Miller [12]. Combining Lemma 7 and Lemma 8, we derive the following bound on possible supported completions across alternating faces, and their enumeration in FPT time.

Let $(D,k)$ and $ℱ$ form an instance of Simple PSCA. We describe a randomized Monte-Carlo algorithm reducing the problem to Dijoin, then show its derandomization. Let us first observe that applying Lemma 28 and Lemma 29 to a solution of $(D,k)$ within $ℱ$ also yields that $(D,k)$ admits a supported solution within $ℱ$, and we may therefore only look for these. Let $c_{𝒮}$ be the maximum number of supported completions given by Corollary 34. By the same corollary, for every face $F\in ℱ$, we can generate in $O(|V(F)|)$ time the set $𝒳(F)$ of all possible restrictions of a minimum supported solution of $D$ to $F$, taking $O(n)$ time across all $ℱ$.

Now, for each such face $F$, we pick a completion $Y^F\in 𝒳(F)$ uniformly at random with probability $1/c_{𝒮}$. With these choices of $Y^F$ made, we create an instance of Dijoin on an auxiliary digraph $D^{\prime }$, that will be equivalent to $(D,k)$ admitting a solution using only these “allowed” arcs. The construction of $D^{\prime }$ starts from the plane $(k+1)$-subdivision of $D$. Then, for each $F\in ℱ$, with local source $S$ and local sink $T$, take any $s\in S$ and $t\in T$, and let us consider the face $F^{\prime }$ resulting from $F$ in $D^{\prime }$. Now, for every $e=(u,v)\in Y^F$, we add a vertex $x_{(u,v)}$, along with: the arc $(x_{(u,v)},u)$, a directed path $P_{s,x_e}$ of length $k+1$ from $s$ to $x_{(u,v)}$, and a directed path $P_{x_{(u,v)},v}$ of length $k+1$ from $x_{(u,v)}$ to $v$. This achieves the construction of $D^{\prime }$, which we stress may not be planar.

We then run the algorithm of [21] for Dijoin on $(D^{\prime },k)$, which by the above decides whether $(D,k)$ admits a solution within ${\bigcup }_{F\in SF}{Y}^F$. Observe that $|A(D^{\prime })|=O(kn)$ and $V(D^{\prime })=O(kn)$, which by Theorem 35 implies a running time of $O(k^3{n}^2)$. We claim that if there is any solution of $(D,k)$ within $ℱ$, the algorithm will output yes with probability at least $1/c_{𝒮}^k$. Indeed, assume this is the case and let $X$ be any minimum supported solution for $(D,k)$ within $ℱ$. Let $ℱ(X)\subseteq ℱ$ be the faces in which $X$ embeds an arc, noting $|ℱ(X)|\le k$. With probability $1/c_{𝒮}^{}{}_{}{}^k$, we have chosen exactly $Y^F=X_F$ for each $F\in ℱ(X)$. Then, since $X$ is indeed a solution of $(D,k)$ in ${\bigcup }_{F\in SF}{Y}^F$, the algorithm for Dijoin will necessarily output yes. This yields a polynomial-time (true-biased) Monte-Carlo algorithm for Simple PSCA which always outputs no when $(D,k)$ admits no solution, and outputs yes with probability at least $1/c_{𝒮}^{}{}_{}{}^k$ when it does. Our algorithm is constructive, because the algorithm for Minimum Dijoin of [21] outputs a solution $X^{\prime }$ for $(D^{\prime },k)$ when it exists. Indeed, recalling the proof of Claim 37, we may transform $X^{\prime }$ into a solution for $(D,k)$ (possibly different from $X$) given by $\{(u,v):(x_{(u,v)},u)\in X^{\prime }\}$.

The process above can be derandomized using universal sets. We follow the terminology of Ullrich and Vybíral [29]. Here, our universal set will be a family $H$ of functions, each mapping a simple face $F\in ℱ$ to an element of $𝒳(F)$. Formally, we take $H$ to be a $(|ℱ|,k,c_{𝒮})$-universal set. That is, for any choice of (at most) $k$ faces $F_1,\mathrm{\dots },F_k\in ℱ$, and any choices $Y_i\in 𝒳(F_i)$ for $i\in [k]$, there is a function $h\in H$ such that $h(F_i)=Y_i$ for every $i$. In particular, for one such $h$, we will have $h(F)=X_F$ for every $F\in ℱ(X)$, since $|ℱ(X)|\le k$. There are explicit constructions of such families $H$ of size $2^{O(k\log c_{𝒮})}\log |ℱ|$, computable in linear time in their size, see Theorem 2.5 in [29] (which relies on [22]). Since $D$ has at most $O(n)$ faces and $c_S$ is a constant, the size of $H$ is $2^{O(k)}\log (n)$. Iterating over the whole universal set yields a factor of $2^{O(k)}\log n$ for the derandomization, and in turn $(D,k)$ can be decided in time $2^{O(k)}{n}^2\log n$. $◀$

Given an instance $(D,k)$, we begin by partitioning $D$ into strong components in $O(n)$ time, see Tarjan [27]. Then, we compute local terminals, as well as the set of alternating faces $𝒜ℱ$ and simple faces $𝒮ℱ$, which takes $O(n)$ time. If the sum of the number of local terminals across alternating faces is greater than $8(k-1)$, we already output No. Indeed, $(D,k)$ must be a negative instance by Observation 14 and Lemma 15. We may thus assume ${\sum }_{F\in 𝒜ℱ}lt(F)\le 8(k-1)$ from now on. We now begin by pre-computing some supported completions of $𝒜ℱ$, before branching over them. Leveraging Corollary 32, we enumerate in time $2^{O(k)}n$ all $2^{O(k)}$ supported completions $Y^{𝒜ℱ}$ of size at most $k$ within alternating faces and record them. Then, for each simple face $F$ of $D$ we enumerate in $O(|V(F)|)$ time all its minimal supported completions, using Corollary 34, taking time $O(n)$ across all simple faces.

We may now branch over the $2^{O(k)}$ completions of $𝒜ℱ$ of size at most $k$ at the cost of only a factor $2^{O(k)}$ to our runtime. In each branch, we consider $D^{\prime }=D+Y^{𝒜ℱ}$ and $k^{\prime }=k-|Y^{AF}|$. Then, we decide whether $(D^{\prime },k^{\prime })$ admits a supported solution within the (initial) simple faces $𝒮ℱ$ by running our algorithm for Simple PSCA from Lemma 36, with $ℱ=𝒮ℱ$, taking time $2^{O(k)}{n}^2\log n$. If the branch corresponding to $Y^{𝒜ℱ}$ outputs yes for $(D^{\prime },k^{\prime })$, letting $Y^{\prime }$ be a solution, it is clear that $Y^{𝒜ℱ}+Y^{\prime }$ is a (supported) solution to $D$. Conversely, assume $(D,k)$ admits a minimum solution $X$, and take it to be supported. In one of our branches, we will have chosen exactly $Y^{𝒜ℱ}=X_{𝒜ℱ}={\cup }_{F\in 𝒜ℱ}{X}_F$. Then, note that $X_{𝒮ℱ}={\cup }_{F\in 𝒮ℱ}{X}_F$ is a supported solution of $(D^{\prime },k^{\prime })$, meaning our algorithm for Simple PSCA $(D^{\prime },k^{\prime })$ will have found a (supported) solution of size at most $|X_{𝒮ℱ}|$, and thus outputs yes. Combining the $2^{O(k)}$ branching and this algorithm yields an algorithm for PSCA running in $2^{O(k)}{n}^2\log n$ time. $◀$