Computing the $(k+2)$-Edge-Connected Components in $k$-Edge-Connected Digraphs in Subquadratic Time

We begin by computing a decomposition of the input digraph $G$, into a collection $H_1,\mathrm{\dots },H_t$ of directed graphs that preserve the $(k+2)$-edge-connected components of $G$. Each graph $H_i$ contains two types of vertices, ordinary and auxiliary, where the ordinary vertices in $H_i$ form a $(k+1)$-edge-connected component of $G$. Moreover, any two vertices $u$ and $v$ of $G$ are $(k+2)$-edge-connected if and only if $u$ and $v$ are $(k+2)$-edge-connected ordinary vertices of a graph $H_i$.

Here, we present a randomized $\tilde{O}(k^{2}m)$-time algorithm that computes the $(k+1)$-edge-connected-component ($(k+1)$-ECC) decomposition of a $k$-edge-connected digraph, for any value of $k$. In addition, we provide a deterministic near-linear-time algorithm that computes the $3$-edge-connected-component ($3$-ECC) decomposition of a general digraph. In both decompositions, the total size of the resulting graphs $H_1,\mathrm{\dots },H_t$ is $O(m)$. To achieve this, we exploit the computation of the nodes corresponding to a poset representation of the minimal $k$-out sets [14, 17] combined with a contraction operation for the $(k+1)$-ECC decomposition and the gadget substitution operation of [21] for the $3$-ECC decomposition. Now, our goal is to partition the ordinary vertices in each graph $H_i$ into $(k+2)$-edge-connected components.

A $(\le k)$-out set $S$ is a set of vertices of $G$ such that there are at most $k$ edges from $S$ to $V\setminus S$. The volume of a vertex set $S$, denoted by $\mathrm{𝑣𝑜𝑙}(S)$, is the number of edges $(v,w)$ whose tail $v$ is in $S$. Chechik et al. [8] considered the problem of computing a $(\le k)$-out set with the following restrictions: Given a graph $G$, a vertex $v$, and two integers $\mathrm{\Delta }$ and $k$ such that $\mathrm{\Delta }\ge k\ge 1$, the goal is to identify a $(\le k)$-out set $S$ such that $v\in S$, all vertices in $S\setminus v$ are reachable from $v$ in $G[S]$, and $vol(S)\le \mathrm{\Delta }$, or to conclude that no such set $S$ exists. [8] described a deterministic algorithm, $\mathrm{𝙻𝚘𝚌𝚊𝚕𝚂𝚎𝚊𝚛𝚌𝚑}(G,v,k,\mathrm{\Delta })$, with $O(\mathrm{\Delta }\cdot k^{2k})$ running time, for the following relaxation of the problem: (i) if there exists a $(\le k)$-out set $S$ such that $v\in S$, all vertices in $S\setminus v$ are reachable from $v$ in $G[S]$, and $vol(S)\le \mathrm{\Delta }$, then $\mathrm{𝙻𝚘𝚌𝚊𝚕𝚂𝚎𝚊𝚛𝚌𝚑}(G,v,k,\mathrm{\Delta })$ returns a $(\le k)$-out set $S^{\prime }$ such that $v\in S^{\prime }$, all vertices in $S^{\prime }\setminus v$ are reachable from $v$ in $G[S^{\prime }]$, and $vol(S^{\prime })\le {(2k)}^{k+2}\mathrm{\Delta }$, and (ii) otherwise it concludes that no such set $S$ exists. Note that if a set $S$ satisfying the constraints exists, then in this relaxed version, procedure $\mathrm{𝙻𝚘𝚌𝚊𝚕𝚂𝚎𝚊𝚛𝚌𝚑}(G,v,k,\mathrm{\Delta })$ returns a set $S^{\prime }$ which satisfies all constraints except the bound on the volume of $S^{\prime }$, which can be larger by a factor of ${(2k)}^{k+2}$. Later on, Forster et al. [12] presented a randomized algorithm for the relaxed version of the problem with $\tilde{O}(\mathrm{\Delta }\cdot k^2)$ running time.

Notice that the algorithms of [8, 12] are useful for , as otherwise the whole vertex set $V(G)$ may be returned. Here, we introduce a slight variant of the local search procedure of [8], that we refer to as $\mathrm{𝙻𝚘𝚌𝚊𝚕𝚂𝚎𝚊𝚛𝚌𝚑𝙵𝚘𝚛𝙼𝚂𝚎𝚝}(G,v,s,k,\mathrm{\Delta })$,which guarantees that the returned set $S^{\prime }$ does not contain $s$. We make use of the following two simple observations: (i) the additional condition, $s\notin S^{\prime }$, implies that we can use the local search procedure without any restriction on the volume $\mathrm{\Delta }$, i.e., it is not necessary to have , and (ii) if $\lambda (v,s)=k$ and $\mathrm{𝑣𝑜𝑙}(M(v))\le \mathrm{\Delta }$, then $\mathrm{𝙻𝚘𝚌𝚊𝚕𝚂𝚎𝚊𝚛𝚌𝚑𝙵𝚘𝚛𝙼𝚂𝚎𝚝}(G,v,s,k,\mathrm{\Delta })$ is guaranteed to return $S^{\prime }=M(v)$.

We say that an $M$-set $M(v)$ is “small” if its volume is at most $m/\sqrt{n}$, and “large” otherwise. Using our modified local search from each vertex $v\ne s$, we can afford to compute all small $M$-sets. In order to account for the partition of the ordinary vertices due to large $M$-sets, we sample the edges uniformly at random. Specifically, by sampling $\tilde{O}(\sqrt{n})$ edges, we can guarantee that for every $M$-set $U$ with volume more than $m/\sqrt{n}$, we have sampled at least one edge $(v,w)$ whose tail $v$ is in $U$ with high probability.

Since we cannot afford to compute all large $M$-sets explicitly, we must instead find a way to exploit the set $M(v)$ associated with each sampled vertex $v$, i.e., the tail of a sampled edge $(v,w)$. To this end, we define a partition $𝒫$ of $V$ to be good for $v$ if:

• $\mathrm{■}$

  $𝒫$ maintains the $(k+2)$-edge-connected components, and

• $\mathrm{■}$

  for every ordinary vertex $u$ such that $v\in M(u)$, the partition $𝒫$ separates any ordinary vertex $w\notin M(u)$ from $u$.

We show that it suffices to compute a partition that is good for each sampled vertex $v$. To construct such partitions efficiently, we distinguish two cases depending on whether $\lambda (v,s)>k$ or $\lambda (v,s)\le k$. In the former case, we exploit the directed acyclic graph (DAG) representation of all minimum cuts introduced by Picard and Queyranne [38]; in the latter, we leverage structural properties of latest minimum cuts. (A latest minimum $(x,y)$-cut is defined as the inclusion-wise maximum $\lambda (x,y)$-out set $S$ such that $x\in S$ and $y\notin S$.)

The framework in [21] required time $\tilde{O}(m\sqrt{m})$; the $\sqrt{m}$ factor appears by balancing the need to hit each component of interest (via random sampling) multiple times, and the time spent on the subsequent backward searches (that depended on the number of times each component was hit). In our framework, we overcome the need for backward searches and achieve a significant improvement in the running time, namely $\tilde{O}(m\sqrt{n})$ for any constant $k$.

The algorithm of Georgiadis et al. [21] repeatedly detects $2$-out sets and $2$-in sets, which are then replaced by connectivity-preserving gadgets of sufficiently small size. These gadgets possess the crucial property of reducing the (out- or in-)volume of the replaced component by a constant factor. This property enables [21] to perform $\mathrm{\Omega }(n)$ local searches, each with a worst-case running time of $\mathrm{\Theta }(m)$, without incurring a total cost of $\mathrm{\Omega }(mn)$. Whenever a sequence of local searches becomes expensive, the corresponding gadget replacement significantly reduces the size of the graph, thereby ensuring a smaller amortized cost. For $k\ge 4$, however, no analogous gadget construction is known that would provide similar guarantees, making it unclear how to afford the time required for $\mathrm{\Omega }(n)$ local searches.

The algorithm of [21] refines the current partition of the ordinary vertices after detecting an $2$-out set or an $2$-in set $S$, by simply separating the vertices inside $S$ from those outside $S$. However, vertices inside $S$ that are not $3$-edge-connected can only be further separated through a recursive call that replaces $V\setminus S$ with a gadget. A key technical difficulty of this approach is that the same edge may participate in multiple recursive calls, making the analysis tedious and heavily dependent on properties specific to the case $k=3$, which do not extend to $k\ge 4$. In contrast, our new framework leverages the structural properties of minimal $k$-out sets, eliminating the need for recursion entirely.

Another major complication in [21] arises from handling intersecting $2$-out sets. Consider a local search initiated from a sampled vertex $v$ that identifies a large $2$-out set $S$. There may exist several $2$-out sets $S_1,\mathrm{\dots },S_k$ that intersect $S$, such that the ordinary vertices in different sets $S_i$ are not $3$-edge-connected. To separate these vertices, it is necessary to identify all such sets $S_1,\mathrm{\dots },S_k$; however, this cannot be achieved through sampling alone, since $S_i\setminus S$ may be very small. To address this issue, [21] employ a sequence of triggered and backward searches, that is, local searches initiated from specific vertices of previously identified $2$-out set sets. Through a complex analysis, they show that it suffices to search for sets of volume $O(\sqrt{m})$, resulting in an overall running time of $\tilde{O}(m\sqrt{m})$. In contrast, our framework completely avoids this complication by exploiting the structural properties of minimal $k$-out sets.

Perhaps the two most technically involved contributions of [21] for the $k=3$ case were the gadget-substitution procedure and the backward searches. Our framework eliminates the need for both, giving an overall significantly simpler algorithm.

Although achieving an $o(mn)$-time algorithm for computing the $k$-edge-connected components of a general digraph, for any fixed constant $k>4$, remains out of reach, we believe that our techniques provide a promising step toward this goal. The main obstacles to attaining such a bound within our framework are the lack of (i) a fast decomposition of a general digraph into $(k-1)$-edge-connected components, and (ii) an efficient algorithm for computing a good partition for a vertex $v$ with $\lambda (v,s)\le k-2$.

Let $s$ be a fixed ordinary vertex of $G$. First, we compute all $M$-sets with volume at most $m/\sqrt{n}$. Specifically, for every ordinary vertex $v\ne s$, we apply the algorithm $\mathrm{𝙻𝚘𝚌𝚊𝚕𝚂𝚎𝚊𝚛𝚌𝚑𝙵𝚘𝚛𝙼𝚂𝚎𝚝}(G,v,s,k+1,\mathrm{\Delta })$, whose guarantees are stated in Proposition 6. Thus, we get a vertex set $S(v)$ such that, if $M(v)\ne \perp$ and $\mathrm{𝑣𝑜𝑙}(M(v))\le m/\sqrt{n}$, then $S(v)=M(v)$. Otherwise, we may still get $M(v)$, or $\mathrm{\varnothing }$. (In any case, we will not get a non-empty output which is distinct from $M(v)$.) Since we apply this procedure for every ordinary vertex $v\ne s$ (and the number of such ordinary vertices may be as large as $n-1$), by Proposition 6 we get an $O((n-1)\cdot m/\sqrt{n})=O(m\sqrt{n})$ time bound for this step. The total output is a collection of $O(n)$ sets of vertices with $O(m/\sqrt{n})$ vertices in each set. We can sort those sets in $O(n\cdot m/\sqrt{n})=O(m\sqrt{n})$ time with bucket sort, and determine the partition ${𝒫}_1$ of the ordinary vertices that have the same $M$-set with volume $O(m/\sqrt{n})$. To be more precise, if for two distinct ordinary vertices $v$ and $v^{\prime }$ we have $S(v)=S(v^{\prime })$, then we put $v$ and $v^{\prime }$ in the same set in ${𝒫}_1$. (And we can put all auxiliary vertices of $G$ in a single set in this partition.) Thus, if two ordinary vertices are $(k+2)$-edge-connected, then they appear in the same set in ${𝒫}_1$.

Now we have to consider the separations induced by the $M$-sets of ordinary vertices with volume larger than $m/\sqrt{n}$. To do this, we first sample enough edges (uniformly, with repetitions allowed) so that, with probability at least $1-\delta$, we have that, for every such “large” $M$-set $U$, we have sampled at least one edge whose tail is in $U$. Thus, it is sufficient to sample $N=\lceil \sqrt{n}{\log }_2(n/\delta )\rceil$ edges. To see this, consider an $M$-set $U$ with volume more than $m/\sqrt{n}$. This means that there are more than $m/\sqrt{n}$ edges whose tail is in $U$. Then, the probability that a randomly chosen edge does not have its tail in $U$ is less than $1-(m/\sqrt{n})/m=1-1/\sqrt{n}$. Thus, the probability that, after $N$ samples, we have not sampled an edge whose tail is in $U$ is less than

Thus, since $n$ is a trivial upper bound on the number of distinct $M$-sets, by the union bound we have that: the probability that there is an $M$-set $U$ with volume more that $m/\sqrt{n}$ for which we have not sampled an edge whose tail is in $U$ is less than $\delta$.

Thus, from now on, we may assume that: for every $M$-set $U$ with volume more than $m/\sqrt{n}$, we have sampled at least one edge whose tail is in $U$ $(\ast )$.

Now, for every tail $v$ of an edge that we have sampled, we do the following. First, we perform at most $k+2$ iterations of Ford-Fulkerson’s algorithm, in order to determine whether $\lambda (v,s)\le k$, or $\lambda (v,s)=k+1$, or $\lambda (v,s)>k+1$. (This takes time $O(km)$.) In the first and second case, we apply Proposition 10 and Proposition 9, respectively, on $v$, in order to get a partition $𝒫(v)$ of $V(G)$ with the guarantess provided by the respective proposition. (Again, this step takes $O(m)$ time.) In the third case (i.e., if $\lambda (v,s)>k+1$), we do nothing. Thus, we get a collection of $O(N)$ partitions of $V(G)$ in total time $O(Nm)=O(\sqrt{n}\log (n/\delta )m)$. We compute the common refinement ${𝒫}_2$ of those partitions with bucket sort, and this takes time $O(nN)$. Then, we return the common refinement of ${𝒫}_1$ and ${𝒫}_2$, which takes $O(n)$ time to be computed. This is how we get a partition $𝒬$. Notice that, by the guarantees of Propositions 10 and 9, we have that $𝒬$ maintains the $(k+2)$-edge-connected components of $G$.

Now we repeat the same process on the reverse graph $G^R$, with the same fixed vertex $s$, and thus we get a partition ${𝒬}_R$. Our final output is the common refinement of $𝒬$ and ${𝒬}_R$.

In order to establish correctness, it remains to show that: if two ordinary vertices $u$ and $w$ are not $(k+2)$-edge-connected, then they appear in distinct sets in the final output. So let $u$ and $w$ be two ordinary vertices that are not $(k+2)$-edge-connected. Then, by Lemma 14 we have that either $M(u)\ne M(w)$ or $M_R(u)\ne M_R(w)$. Let us assume, w.l.o.g., that $M(u)\ne M(w)$. Now, if either $\mathrm{𝑣𝑜𝑙}(M(u))\le m/\sqrt{n}$ or $\mathrm{𝑣𝑜𝑙}(M(w))\le m/\sqrt{n}$, then $u$ and $w$ are separated by ${𝒫}_1$, and thus by the final output. Otherwise, for each of $u$ and $w$ we have that its $M$-set is either $\perp$, or it has volume more than $m/\sqrt{n}$, but they cannot both be $\perp$. Now, since $M(u)\ne M(w)$, by Lemma 15 we have that either $M(u)\ne \perp$ and $w\notin M(u)$, or $M(w)\ne \perp$ and $u\notin M(w)$. Thus, we may assume, w.l.o.g., that $M(u)\ne \perp$ and $w\notin M(u)$. Now, since $\mathrm{𝑣𝑜𝑙}(M(u))>m/\sqrt{n}$, our assumption $(\ast )$ implies that we have sampled at least one edge whose tail $v$ is in $M(u)$. Then, we obviously have that $\lambda (v,s)\le k+1$, and therefore one of Propositions 10 and 9 (depending on whether $\lambda (v,s)\le k$ or $\lambda (v,s)=k+1$, respectively), implies that $𝒫(v)$ separates $u$ and $w$. Thus, $u$ and $w$ are separated by the final output.

(Notice that our assumption $(\ast )$ holds on $G$ with probability more than $1-\delta$. However, we want the same assumption to hold simultaneously for $G$ and $G^R$ with probability more than $1-\delta$. Thus, we should have chosen $\delta$ to be half of the desired probability of failure, so that, by the union bound, this assumption is satisfied simultaneously in $G$ and $G^R$ with the desired probability of success.) $◀$

If we drop the assumption that $k$ is a fixed constant, then, by relying throughout on the deterministic local search procedure of Proposition 6, there is an exponential dependency on $k$ in the time bound for computing the $(k+2)$-edge-connected components. We can improve this dependency to polynomial, by using instead the randomized local search procedure of Proposition 7. The local search procedure is used in two different places in our framework: in the algorithm for computing the $(k+1)$-ECC-decomposition (Theorem 3), and in the search for small $M$-sets in Line 3 of Algorithm 1.

In particular, if we want to have the same guarantees for Algorithm 1 as in the statement of Theorem 5, but with a running time of $O(k^{2}m\sqrt{n}\log (n/\delta ))$, then we must replace the local search procedure in Line 3 with that provided by Proposition 7, and repeat it for $\lceil \log (4n/\delta )\rceil$ times for every vertex $v\ne s$. This is in order to get a $\delta /(4n)$ bound on the probability of failure for every vertex $v\ne s$, for the search for small $M$-sets in each direction (i.e., in $G$ and in $G^R$), so that the union bound gives a $\delta /2$ bound on the probability of failure for this search in both directions. Furthermore, we must increase the sampling rate in Line 5 from $\lceil \sqrt{n}{\log }_2(2n/\delta )\rceil$ to $\lceil \sqrt{n}{\log }_2(4n/\delta )\rceil$, in order to also get a $\delta /2$ bound on the probability of failure for the search for large $M$-sets (in both directions). Thus, by the union bound, the total probability of failure of Algorithm 1 can be bounded by $\delta$.

Overall, in order to establish Theorem 1, we need as input the graph $G$, and the parameters $k$ and $\delta$. First, we employ the randomized decomposition of Theorem 3, which runs in $\tilde{O}(k^{2}m)$ time and produces a correct decomposition $H_1,\mathrm{\dots },H_t$ with probability at least $1-\delta /2$. Then, for each graph $H_i$, we apply Algorithm 1 with bound $\delta /(2n)$ on the probability of failure. This is because: first, there are at most $n$ graphs $H_i$ on which we apply this algorithm, and second, each of those graphs has at most $n$ ordinary vertices (that correspond to vertices of the original graph). Thus, the union bound establishes the $\delta$ bound on the probability of failure for computing the $(k+2)$-edge-connected components of the original graph $G$.

Due to the submodularity of the cut function, we have $\mathrm{𝑜𝑢𝑡}(S\cap S^{\prime })+\mathrm{𝑜𝑢𝑡}(S\cup S^{\prime })\le \mathrm{𝑜𝑢𝑡}(S)+\mathrm{𝑜𝑢𝑡}(S^{\prime })$, and therefore $\mathrm{𝑜𝑢𝑡}(S\cap S^{\prime })+\mathrm{𝑜𝑢𝑡}(S\cup S^{\prime })\le 2k$. Notice that both $S\cap S^{\prime }$ and $S\cup S^{\prime }$ are cuts that separate $X$ and $Y$. Thus, since $\lambda (X,Y)=k$, we have $\mathrm{𝑜𝑢𝑡}(S\cap S^{\prime })\ge k$ and $\mathrm{𝑜𝑢𝑡}(S\cup S^{\prime })\ge k$. Therefore, we have $2k\le \mathrm{𝑜𝑢𝑡}(S\cap S^{\prime })+\mathrm{𝑜𝑢𝑡}(S\cup S^{\prime })$, and thus we infer that $\mathrm{𝑜𝑢𝑡}(S\cap S^{\prime })=k$ and $\mathrm{𝑜𝑢𝑡}(S\cup S^{\prime })=k$. $◀$

We will be using the following corollary throughout, without explicitly invoking it.

Consider the collection $𝒮$ of all $k$-out sets that separate $X$ and $Y$. Then, Lemma 12 implies that $\bigcap 𝒮$ is a $k$-out set that separates $X$ and $Y$. Similarly, Lemma 12 implies that $\bigcup 𝒮$ is a $k$-out set that separates $X$ and $Y$. $◀$

Let $Z$ be a set of vertices of $G$, and let $G_Z$ be the graph that is formed by contracting $Z$ into a single vertex $z$. If $X$ is a set of vertices of $G_Z$, then we let $X^{\prime }$ denote $X$ if $z\notin X$, and $(X\setminus \{z\})\cup Z$ otherwise. (I.e., $X^{\prime }$ is the “uncontraction” of $X$ in $G$.) Then it is easy to see that, for every set of vertices $S$ of $G_Z$, we have ${\mathrm{𝑜𝑢𝑡}}_{G_Z}(S)\ge {\mathrm{𝑜𝑢𝑡}}_G(S^{\prime })$. This implies that, for every two disjoint sets of vertices $X$ and $Y$ of $G_Z$, we have ${\lambda }_{G_Z}(X,Y)\ge {\lambda }_G(X^{\prime },Y^{\prime })$. (I.e., the process of contracting vertices can only increase the edge connectivity.)

Since $u$ and $w$ are not $(k+2)$-edge-connected (but they are $(k+1)$-edge-connected), we may assume, w.l.o.g., that there is a $(k+1)$-cut $S$ that separates $u$ and $w$. Now there are two possibilities: either $s\notin S$, or $s\in S$. Let us first consider the case that $s\notin S$. Then, $S$ is a $(k+1)$-cut that separates $u$ and $s$, and therefore $M(u)$ exists and $M(u)\subseteq S$. Then, since $w\notin S$, we have $w\notin M(u)$. Therefore, we infer that either $M(w)$ does not exist, or $M(w)\ne M(u)$ (because, if $M(w)$ exists, it satisfies $w\in M(w)$). Now let us assume that $s\in S$. Then, $V\setminus S$ is a $(k+1)$-cut in $G^R$ that separates $w$ and $s$. Thus, we have $M_R(w)\subseteq V\setminus S$, and $u\notin M_R(w)$. Therefore, we infer, as previously, that either $M_R(u)$ does not exist, or $M_R(u)\ne M_R(w)$. $◀$