# A Nearly Time-Optimal Distributed Approximation of
Minimum Cost $k$-Edge-Connected Spanning Subgraph

Michal Dory
University of Haifa
<EMAIL_ADDRESS>
Mohsen Ghaffari
MIT
<EMAIL_ADDRESS>
The minimum-cost $k$-edge-connected spanning subgraph ($k$-ECSS) problem is a
generalization and strengthening of the well-studied minimum-cost spanning
tree (MST) problem. While the round complexity of distributedly computing the
latter has been well-understood, the former remains mostly open, especially as
soon as $k\geq 3$.

In this paper, we present the first distributed algorithm that computes an
approximation of $k$-ECSS in sublinear time for general $k$. Concretely, we
describe a randomized distributed algorithm that, in
$\tilde{O}(k(D+k\sqrt{n}))$ rounds, computes a $k$-edge-connected spanning
subgraph whose cost is within an $O(\log n\log k)$ factor of optimal. Here,
$n$ and $D$ denote the number of vertices and diameter of the graph,
respectively. This time complexity is nearly optimal for any
$k=\mathop{\mathrm{missing}}{poly}(\log n)$, almost matching an
$\tilde{\Omega}(D+\sqrt{n/k})$ lower bound. Our algorithm is the first to
achieve a sublinear round complexity for $k\geq 3$. We note that this case is
considerably more challenging than the well-studied and well-understood $k=1$
case—better known as MST—and the closely related $k=2$ case.

Our algorithm is based on reducing the $k$-ECSS problem to $k$ set cover
instances, in which we gradually augment the connectivity of the spanning
subgraph. To solve each set cover instance, we combine new structural
observations on minimum cuts with graph sketching ideas. One key ingredient in
our algorithm is a novel structural lemma that allows us to compress the
information about _all minimum cuts_ in a graph into a succinct
representation, which is computed in a decentralized fashion. We hope that
this succinct representation may find applications in other computational
settings or for other problems.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
    2. 1.2 Our Techniques
    3. 1.3 Additional Related Work
  2. 2 High-Level Description of the Algorithm
    1. 2.1 Estimating the Cost-Effectiveness when $T$ is a Path
      1. 2.1.1 Succinct Representation of Min Cuts
      2. 2.1.2 Estimating the Cost-Effectiveness via Graph Sketches
    2. 2.2 Estimating the Cost-Effectiveness for a General Spanning Tree $T$
  3. 3 Discussion
  4. 4 Preliminaries
    1. 4.1 Cover Values and 2-respecting Cuts
    2. 4.2 Fragment Decomposition
    3. 4.3 LCA Labels
    4. 4.4 Basic Notation and Tools
  5. 5 Distributed Greedy Algorithm for Connectivity Augmentation
    1. 5.1 The Algorithm for $Aug_{k}$
    2. 5.2 Analysis
  6. 6 Succinct Representation of Min Cuts
    1. 6.1 A Proof for a General Tree
  7. 7 Learning the Cut Information
    1. 7.1 The Algorithm for Non-Highways
    2. 7.2 The Algorithm for Highways
  8. 8 Computing the Cost-Effectiveness
    1. 8.1 Computing Sketches
    2. 8.2 Learning the Cut Names
    3. 8.3 Putting Everything Together
  9. A Lower Bounds
    1. A.1 Construction with Parallel Edges
    2. A.2 Construction without Parallel Edges
  10. B Missing Proofs from Section 5
  11. C Missing Proofs from Section 6

##  1 Introduction

The minimum cost $k$-edge connected spanning subgraph problem is one of the
most central problems in the area of network design [Jai01, KV94, CT00,
GGTW09, GG12, GGP+94, CHN+22]. Consider a network of computers with a
prescribed list of possible connection links, where using each particular link
incurs a certain cost—e.g., a monetary cost that should be paid to the
Internet service provider. In the area of network design, the task is to
choose a set of links (e.g., which will be purchased from the provider) that
minimizes our cost while meeting certain (connectivity) requirements. For
instance, we might want that the chosen links form a connected spanning
subgraph; this is exactly the well-known minimum-cost spanning tree (MST)
problem. Or we might want a stronger subgraph, which remains connected even if
a small number of edges fail. The latter is known as the _minimum-cost
$k$-edge-connected spanning subgraph_ ($k$-ECSS) problem and is the focus of
this paper. More precisely, in the $k$-ECSS problem, the objective is to find
a minimum cost $k$-edge-connected spanning subgraph $H$ of the given graph
$G$. As standard, we say that a graph $H$ is $k$-edge-connected if it remains
connected after the removal of any $k-1$ edges. Notice that MST is a special
case of $k$-ECSS where $k=1$.

##### Centralized Algorithms.

Centralized approximation algorithms for $k$-ECSS are based on various
techniques including a reduction of the problem to a matroid intersection
problem in directed graphs [KV94], the primal-dual algorithm of Goemans et al.
[GGP+94], and the iterative rounding algorithm of Jain [Jai01]. At best these
algorithms obtain a 2-approximation for weighted $k$-ECSS [Jai01, KV94]. We
note that these centralized algorithms are somewhat slow: The fastest
2-approximation algorithm [KV94] takes $O(mnk)$ time. A recent work of
Chalermsook et al. [CHN+22] provides a $2+\epsilon$ approximation, for
constant $\epsilon>0$, in $\tilde{O}(m+k^{2}n^{1.5})$-time. More importantly
for this paper, none of these algorithms is suitable for the distributed
setting.

##### Distributed Algorithms.

Since a primary motivation for the $k$-ECSS problem comes from the reliability
of networks— e.g., with the goal of building a low-cost (communication)
backbone resistant to failures—it is imperative to study the problem also from
the perspective of distributed algorithms that allow the network of computers
to autonomously compute the solution to the $k$-ECSS problem. We focus on the
distributed Congest model: The communication network is equal to the input
graph $G$, and vertices communicate by exchanging $O(\log{n})$ bit messages
with their neighbors in synchronous rounds. The input and output are local. In
the beginning, each vertex only knows the weights of the edges adjacent to it,
and at the end, it should know which of the edges adjacent to it are in the
spanning subgraph constructed. The main complexity measure is the number of
communication rounds.

While there has been some recent progress in understanding the complexity of
$k$-ECSS in the Congest model, currently there are efficient algorithms only
for very special cases of the problem, as we overview next. These special
cases are significantly easier from a technical perspective.

  * •

Unweighted Graphs: First, if one wants to solve the _unweighted_ version of
the $k$-ECSS problem, a very simple algorithm based on iteratively
constructing spanners gives an $O(1)$-approximation in $O(k\log^{1+o(1)}{n})$
time [Par19]. This was recently improved to a $(2+\epsilon)$-approximation in
$\mathop{\mathrm{missing}}{poly}(\log n)$ rounds by Bezdirghin et al [BEG+22].
Unfortunately, these approaches do not extend to weighted graphs at all,
because in the weighted case even adding one redundant edge can be too
expensive and might destroy the approximation guarantee.

  * •

Weighted Graphs with $k=1$: The case $k=1$ in weighted graphs is just the
minimum weight spanning tree problem (MST), which is a widely studied and
well-understood problem in distributed computing. See, e.g., [GHS83, GKP98,
KP98, Elk06, Elk17, PRS17, FO21]. It is well-known that the MST problem can be
solved in $O(D+\sqrt{n}\log^{*}{n})$ time [KP98] for graphs with $n$ vertices
and diameter $D$, and that this time complexity is nearly tight, essentially
matching an $\Omega(D+\sqrt{\frac{n}{\log{n}}})$ lower bound [PR00, Elk06,
SHK+12].

  * •

Weighted Graphs with $k=2$: For the case $k=2$, a recent line of research
[CHD20, Dor18, DG19] leads to a $(5+\epsilon)$-approximation in
$\tilde{O}(D+\sqrt{n})$ time [DG19], nearly matching the complexity of the MST
problem. A 3-approximation can be obtained in $O(n)$ time [CHD20].

  * •

Weighted Graphs with $k\geq 3$: For larger values of $k$, the fastest
algorithms require at least _linear_ time. The first algorithm for the problem
is an $O(knD)$-round $O(\log{k})$-approximation algorithm [Sha09] based on the
primal-dual algorithm of Goemans et al. [GGP+94]. A later result shows an
$O(k\log{n})$-approximation in $\tilde{O}(kn)$ rounds [Dor18]. This complexity
remains at least linear and also it is still way above the
$\tilde{O}(D+\sqrt{n})$ complexity obtained for $k\leq 2$.

Despite the above progress, the general question (general $k$ and arbitrary
weights) remains mostly open. In particular, the following remains unanswered:

######  Question 1.1.

Is it possible to solve the $k$-ECSS problem in sublinear time for $k\geq 3$?

As we will discuss later in-depth, the core of the technical challenge in
answering this question lies in the following issue: in solving the $k$-ECSS
problem, we somehow have to deal with all the minimum size cuts of the
hitherto selected subgraph and make sure to include edges so that no cut of
size $k^{\prime}=k-1$ remains. The complexity of this task changes
significantly once $k\geq 3$. The intuitive reason is that when the minimum
cut size (in the subgraph selected so far) is $k^{\prime}=k-1\geq 2$, the
minimum cuts can have much more complex structures and overlaps, in comparison
with the special cases where $k^{\prime}\in\\{0,1\\}$. In those two special
cases, there are fairly simple characterizations of all min cuts, which open
the road for efficient algorithms: In particular, when $k^{\prime}=0$, minimum
cuts are exactly defined by the connected components. When $k^{\prime}=1$, if
we fix any spanning tree $T$, minimum-cuts are exactly those edges $e$ of $T$
for which there is no other edge between the two components of
$T\setminus\\{e\\}$. When $k\geq 3$ and thus $k^{\prime}=k-1\geq 2$, minimum
cuts can have much more complicated structures. We will discuss this case in
Section 1.2.

###  1.1 Our Results

In this paper, we answer 1.1 in the affirmative, proving the following.

######  Theorem 1.2.

There is a randomized distributed algorithm in the Congest model that computes
an $O(\log{k}\log{n})$-approximation of the minimum cost $k$-edge-connected
spanning subgraph problem in $\tilde{O}(k(D+k\sqrt{n}))$ time, with high
probability.111As standard, the phrase “with high probability” (w.h.p)
indicates probability at least $1-\frac{1}{n^{c}}$ for a constant $c\geq 1$.

##### Remark on near-optimality of time complexity.

For $k=\mathop{\mathrm{missing}}{poly}(\log n)$, we get a complexity of
$\tilde{O}(D+\sqrt{n})$, nearly matching the complexity of previous algorithms
for $k\leq 2$. The complexity is nearly tight due to a lower bound we show in
Appendix A. Concretely, by extending lower bounds from [SHK+12, CHD20, GK13a],
we prove that obtaining any polynomial approximation requires
$\tilde{\Omega}(D+\sqrt{n})$ rounds for graphs that allow parallel edges, and
$\tilde{\Omega}(D+\sqrt{n/k})$ rounds for simple graphs. Moreover, our
algorithm is the first sublinear time algorithm for a wide range of parameters
$k$.

##### Remark on approximation factor.

We remark that while there are centralized algorithms that obtain a
2-approximation for $k$-ECSS, obtaining such an approximation for non-
centralized algorithms seems a highly challenging task. All the previous
distributed approximation algorithms for general $k$-ECSS had higher
approximation ratios of $O(k\log{n})$ [Dor18] or $O(\log{k})$ [Sha09] (with a
much higher $O(knd)$ time complexity). Such high approximation have been
studied in other modern computation settings, e.g., in the online centralized
setting, where an $O(k\log^{3}{n})$-approximation was obtained by Gupta et al.
[GKR12]. For a comparison with prior work, see Table 1.

Reference |  Variant |  Approximation |  Time complexity
---|---|---|---
Kutten and Peleg [KP98] |  $k=1$ |  exact |  $\tilde{O}(D+\sqrt{n})$
Censor-Hillel and Dory [CHD20] |  $k=2$ |  $3$ |  $O(n)$
Dory and Ghaffari [DG19] |  $k=2$ |  $5+\epsilon$ |  $\tilde{O}(D+\sqrt{n})$
Shadeh [Sha09] |  general $k$ |  $O(\log{k})$ |  $O(knD)$
Dory [Dor18] |  general $k$ |  $O(k\log{n})$ |  $\tilde{O}(kn)$
Here |  general $k$ |  $O(\log{k}\log{n})$ |  $\tilde{O}(k(D+k\sqrt{n}))$
Table 1: Algorithms for weighted $k$-ECSS. Note that for $k\geq 3$, prior to
this work, no sublinear time algorithm was known. Also, we believe that cases
with small values of $k$—e.g., constant or at most polylogarithmic—are
arguably the most relevant cases, from a practical perspective.

##### Remark on bicriteria approximation for larger $k$.

We also note that by using a simple combination of Theorem 1.2 with Karger’s
well-known uniform edge sampling results [Kar93], we can obtain the following
bicriteria algorithm, which has a better round complexity and approximation
guarantee for larger $k$. For the proof, see Section 8.3.

######  Corollary 1.3.

There is a randomized distributed algorithm in the Congest model that computes
a $k(1-o(1))$-edge-connected spanning subgraph whose cost is within an $O(\log
n\log\log n)$ factor of the minimum cost $k$-edge-connected spanning subgraph,
in $\tilde{O}(k(D+\sqrt{n}))$ time, with high probability.

###  1.2 Our Techniques

While there are many centralized algorithms for $k$-ECSS, they do not seem
applicable in the distributed setting. Instead, the high-level outline of our
algorithm is to use a simple and natural approach, based on [Dor18], where we
iteratively augment the connectivity of the chosen subgraph, gradually
increasing connectivity from $0$ to $k$. In particular, we start with an empty
subgraph $H$, and we augment its connectivity in $k$ iterations, where in
iteration $i$ we augment the connectivity from $i-1$ to $i$; this is indeed
the technical core of the problem. This augmentation problem can be seen as a
special case of the _set cover_ problem, where the goal is to _cover_ cuts of
size $i-1$ in $H$ by a low-cost set of edges, according to the following
definition. Here we say that an edge $e$ covers a cut $C$ in $H$ if
$(H\setminus C)\cup\\{e\\}$ is connected. To obtain a good approximation, our
goal is to add a low-cost set of edges that augments the connectivity.

To decide which edges to add, we compare edges according to their _cost-
effectiveness_ , defined as $\rho(e)=\frac{|C_{e}|}{w(e)}$, where $C_{e}$ is
the set of minimum cuts that $e$ covers in $H$, and $w(e)$ is the weight of
$e$. Intuitively, adding edges with large values of cost-effectiveness allows
us to cover many cuts while paying a low cost. To exploit this, we use an
approach similar to greedy set cover solutions, in which per step we add to
the augmentation a set of edges with near-maximal cost-effectiveness.

The main challenge in obtaining a fast algorithm using this approach is to
design an efficient algorithm for estimating the cost-effectiveness of edges,
and that is exactly the main technical contribution of our paper. In [Dor18],
it is shown that in the special case that the minimum cut size is 1, the cost-
effectiveness can be computed in $\tilde{O}(D+\sqrt{n})$ time. That leads to
an $\tilde{O}(D+\sqrt{n})$-round algorithm for 2-ECSS. However, dealing with
cuts of size at least 2 is much more challenging, due to the possibility of
more complex interactions and overlaps between these cuts, and no sublinear-
time or even linear time algorithm is known for general $k$.

##### Our Approach for Approximating Cost-Effectivenesses.

Our main technical contribution in this paper is to provide a sublinear-time
algorithm for approximating cost-effectivenesses. This involves presenting a
structural lemma about min-cuts and providing a novel succinct representation
of them, which can also be computed efficiently using a relatively simple and
local scheme. We hope that these properties may find applications in other
problems and/or computational settings.

Intuitively, to compute the cost-effectiveness, we may want to be able to
learn about all minimum cuts in the graph $H$, and then let each edge $e$
check which ones of them it covers. However, a direct implementation of this
approach seems quite expensive. We do something different. Our algorithm has
two main parts.

  1. 1.

Succinct Representation of Minimum Cuts. First, we show a structural lemma,
which allows us to compress efficiently information about minimum cuts. Using
it, each edge learns a small amount of information that represents the minimum
cuts it participates in.

  2. 2.

Estimating the Cost-Effectiveness via Graph Sketches. Second, we show that we
can use the information computed above combined with graph sketches to
estimate for each edge how many cuts it covers.

In Section 2, we explain in detail the high-level ideas behind these
ingredients.

###  1.3 Additional Related Work

Minimum Cut. The minimum cut problem is a well-studied problem. In the
distributed Congest model, a rich line of work [PT11, GK13a, NS14, DHNS19,
GNT20, Par19, DEMN21, GZ22], led to a near-optimal algorithm taking
$\tilde{O}(D+\sqrt{n})$ time for computing the minimum cut in a weighted graph
[DEMN21]. We remark that distributed min cut algorithms usually focus on
finding one minimum cut, while in our work here we had to work with all the
minimum cuts in a graph. For this reason, we believe that our approach can
find future applications for other problems related to minimum cuts, for
example for estimating the number of minimum cuts in a graph.

Connectivity Certificates. Another related problem studied in the distributed
setting is the problem of finding sparse connectivity certificates [Par19,
BEG+22, DHNS19]. A sparse connectivity certificate of a graph $G$, is a
subgraph $H$ of size $O(kn)$ that is $k$-edge-connected if and only if $G$ is
$k$-edge-connected. Sparse connectivity certificates can be used to obtain
$O(1)$-approximation for the _unweighted_ version of $k$-ECSS. In particular,
the construction in [BEG+22] gives a $(2+\epsilon)$-approximation for
unweighted $k$-ECSS in $\mathop{\mathrm{missing}}{poly}(\log n)$ rounds.
Obtaining this approximation in _unweighted_ graphs is based on showing that
the subgraph built is sparse, and combine it with the fact that any $k$-edge-
connected subgraph has at least $kn/2$ edges. One common approach to build
connectivity certificates is based on iteratively building spanning trees or
spanners. While this approach can also be implemented in weighted graphs,
unfortunately it does not lead to any meaningful approximation for weighted
$k$-ECSS, the reason is that in the weighted case even adding one redundant
edge can be too expensive, and it is not enough to count the number of edges
in the subgraph constructed anymore.

Fault-Tolerant Structures. In the $k$-ECSS problem the goal is to build a low-
cost subgraph that remains connected after edge failures. This is closely
related to fault-tolerant graph structures, sparse graphs that maintain a
certain functionality (for example, contain an MST or a spanner) after
failures. Distributed algorithms for building fault-tolerant BFS and MST
structures that are resilient to one edge failure appear in [GP16], where
distributed fault-tolerant BFS trees and distance preserves resilient to two
edge failures appear in [Par20]. Dealing with more failures is an open
question. Distributed algorithms for fault-tolerant spanners appear in [DK11,
DR20, Par22].

##  2 High-Level Description of the Algorithm

As explained in Section 1.2, to solve $k$-ECSS, we follow a distributed greedy
approach described in [Dor18], that reduces the $k$-ECSS problem to the
problem of estimating cost-effectiveness of edges. A detailed discussion of
this reduction appears in Section 5. Our main technical contribution is
providing a method that computes the cost-effectiveness of all edges
efficiently.

######  Theorem 2.1.

[Cost-Effectiveness Approximation] Let $H$ be an $i$-edge-connected spanning
subgraph of a graph $G$. For an edge $e\not\in H$ define $C_{e}$ as the set of
cuts of size $i$ in $H$ covered by $e$. Then in $\tilde{O}(D+i\sqrt{n})$ time
each edge $e\not\in H$ learns an $O(1)$-approximation of the value $|C_{e}|$.
In particular, edge $e$ learns an $O(1)$-approximation of its cost-
effectiveness with respect to $H$, defined by $\rho(e)=\frac{|C_{e}|}{w(e)}.$
The algorithm works with high probability.

##### Reduction to 2-respecting cuts.

To estimate the cost-effectiveness, we should estimate for each edge the
number of cuts it covers. Our first step is to simplify the structure of the
problem. We use Karger’s well-known reduction [Kar00], which allows us to work
with only _2-respecting cuts_ with respect to a certain tree, instead of
working with arbitrary minimum cuts. We say that a cut $C$ _2-respects_ a
spanning tree $T$ if $|C\cap T|\leq 2$. Based on [Kar00], we show in Section 4
that in order to estimate the cost-effectiveness of edges it is enough to
estimate for each edge the number of min 2-respecting cuts it covers in a
certain spanning tree $T$. A min 2-respecting cut is a minimum cut in $G$ that
has at most 2 edges in $T$. For full details and proofs see Section 4. From
now on we fix a spanning tree $T$ of a graph $H$ and focus on estimating the
number of min 2-respecting cuts each edge $e\not\in T$ covers. Note that any
min 2-respecting cut has (at most) 2 tree edges $t,t^{\prime}$, we identify
the cut with these edges. A cut that has only one tree edge $t$ is called a
1-respecting cut.

###  2.1 Estimating the Cost-Effectiveness when $T$ is a Path

To simplify the presentation, we start by focusing on the special case that
$T$ is a path, which already allows us to present many of the key ingredients
of the algorithm. For a non-tree edge $e=\\{u,v\\}$, we denote by $P_{e}$ the
tree path between $u$ and $v$. We start with the following simple observation
that we prove in Section 4. See Figure 1 for an illustration.

######  Claim 2.2.

A non-tree edge $e$ covers a 2-respecting cut $\\{t,t^{\prime}\\}$ iff exactly
one of $t,t^{\prime}$ is in $P_{e}$.

We next give an intuition for the proof (for the case that $T$ is a path).
First note that if $\\{t,t^{\prime}\\}$ is a minimum 2-respecting cut, that
represents a minimum cut $C$ in a graph $H$, then $\\{t,t^{\prime}\\}$ are the
only edges of $C$ in $T$, and $H\setminus C$ has exactly two connected
components. We can identify them as follows. Removing $\\{t,t^{\prime}\\}$
from $T$ disconnects $T$ to 3 sub-paths $P_{1},P_{2},P_{3}$, where the
2-respecting cut defined by $\\{t,t^{\prime}\\}$ has 2 sides (as this is a
minimum cut), one has the middle path $P_{2}$ and the other has the two other
paths $P_{1}\cup P_{3}$. The reason is that $\\{t,t^{\prime}\\}$ are edges
that cross the cut, and they already have one endpoint in $P_{2}$, hence their
other endpoints are in the other side of the cut. Now the edges that cross the
cut are exactly those that have one endpoint in $P_{2}$ and the other in
$P_{1}\cup P_{3}$, which are edges $e$ where exactly one of
$\\{t,t^{\prime}\\}$ is in $P_{e}$. The proof also generalizes to the case
that $T$ is a general spanning tree (see Section 4).

Figure 1: The tree $T$ is the path from $u$ to $v$. The edges $e_{1},e_{2}$
are examples of non-tree edges that cover the 2-respecting cut
$\\{t,t^{\prime}\\}$. This 2-respecting cut is is the blue-grey cut in the
figure, where one side is $P_{1}\cup P_{3}$, and the other side is $P_{2}$.

As we show in Section 4, if the endpoints of $e$ already know about the min
2-respecting cut $\\{t,t^{\prime}\\}$, then using 2.2 and the tool of _lowest
common ancestor (LCA) labels_ (see Section 4), we can check if $e$ covers the
min 2-respecting cut $\\{t,t^{\prime}\\}$. Basically we just need to compare
the endpoints of $e,t,t^{\prime}$ and identify if exactly one of
$\\{t,t^{\prime}\\}$ is in $P_{e}$, which can be done using LCA labels. Hence,
a naive approach for estimating the cost-effectiveness could be first to learn
about all the min 2-respecting cuts $\\{t,t^{\prime}\\}$ in the graph, and
then for each one of them to check if $e$ covers $\\{t,t^{\prime}\\}$.

There are however two problems with this approach. It requires _finding_ all
min 2-respecting cuts in the graph, and _broadcasting_ this information to the
whole graph. It is not clear if it is possible to find all min 2-respecting
cuts efficiently. Very recently, it was shown that it is possible to find
_one_ min 2-respecting cut in $\tilde{O}(D+\sqrt{n})$ time. This led to a
near-optimal distributed min cut algorithm [DEMN21]. However, their algorithm
crucially relies on the fact that only one minimum cut should be found and it
does not explore all possible options for min cuts. Moreover, even if there
was a distributed algorithm that finds all possible cuts, the number of
minimum cuts in the graph could be $\Omega(n^{2})$, and hence broadcasting
information about all min 2-respecting cuts to the whole graph cannot lead to
an efficient algorithm.

We next describe our general approach to overcome the above problems. One of
the key insights of this paper (which we hope may find applications in other
computation settings and/or for other problems) is this: Instead of learning
about all min 2-respecting cuts and broadcasting this information to the whole
graph, we show that each tree edge $t$ can learn a _compressed_ description of
the min 2-respecting cuts of the form $\\{t,t^{\prime}\\}$. More concretely,
we show that if the minimum cut size is $k$, then we can represent in
$O(k\log{n})$ bits a compressed information of all minimum 2-respecting cuts
$\\{t,t^{\prime}\\}$ that a tree edge $t$ appears in. Second, we show that all
tree edges $t$ can learn their compressed information efficiently, and we show
how to use it to evaluate the cost-effectiveness of non-tree edges. We next
provide more details on these ingredients.

####  2.1.1 Succinct Representation of Min Cuts

In Section 6, we show that while there could be many minimum 2-respecting
cuts, there is a succinct way to represent them. To get an intuition, think
about a simple case that the graph $G$ is just a cycle, and the spanning tree
$T$ is a path. Here any 2 edges in the graph are a cut, so listing all the
cuts in the graph would take $\Omega(n^{2})$ space. However, if we look at
some tree edge $t$, there is a very simple way to represent all the
2-respecting cuts it participates in, these are just all the edges in $T$. We
prove a structural lemma that generalizes this simple observation to a general
tree with minimum cut of size $k$. Concretely, we show that each tree edge $t$
can learn $O(k\log{n})$ bits that represent all the minimum 2-respecting cuts
of the from $\\{t,t^{\prime}\\}$. We call this information
$\mathsf{CutInfo}(t)$. This information contains a description of $O(k)$
subpaths in the tree, where in each one of them there is a simple criterion to
check if a tree edge $t^{\prime}$ is in a min 2-respecting cut with $t$. We
emphasize that $t$ does not learn about all the min 2-respecting cuts
$\\{t,t^{\prime}\\}$, as this could be a lot of information. Instead, given
$\mathsf{CutInfo}(t)$ and a tree edge $t^{\prime}$, it is possible to deduce
whether $\\{t,t^{\prime}\\}$ is a min 2-respecting cut or not. Let us fix some
notation. We denote by $\mathsf{Cut}(t,t^{\prime})$ the size of the
2-respecting cut defined by the tree edges $t,t^{\prime}$ (i.e., the number of
edges that cross the cut). We denote by $\mathsf{Cov}(t)$ the number of edges
that _cover_ a tree edge $t$. Here we say that an edge $e=\\{u,v\\}$ covers a
tree edge $t$ if $t$ is in the unique tree path $P_{e}$ between $u$ and $v$.
In particular, $t$ covers $t$. We denote by $\mathsf{Cov}(t,t^{\prime})$ the
number of edges that cover both $t$ and $t^{\prime}$. From 2.2, we get that
$\mathsf{Cut}(t,t^{\prime})=\mathsf{Cov}(t)+\mathsf{Cov}(t^{\prime})-2\mathsf{Cov}(t,t)$.
This follows from the fact that the edges that cross (or cover) the cut are
exactly the ones that cover exactly one of $t,t^{\prime}$. We show the
following.

######  Lemma 2.3.

[Succinct Representation of Min Cuts] Let $G=(V,E)$ be a graph with minimum
cut size $k$, and let $T$ be a spanning tree of $G$. Fix a tree edge $t\in T$.
Then there exist $\ell=O(k)$ tuples $\\{(S^{t}_{i},c^{t}_{i})\\}_{1\leq
i\leq\ell}$ where each $S^{t}_{i}$ is a subpath in the tree, such that the
edges $t^{\prime}$ where $\mathsf{Cut}(t,t^{\prime})=k$ are exactly all edges
in $E_{t}=\cup_{1\leq i\leq\ell}\\{t^{\prime}\in
S^{t}_{i}|\mathsf{Cov}(t^{\prime})=c^{t}_{i}\\}$.

Let us provide an intuition of the proof of this Succinct Representation Lemma
when $T$ is a path (see Figure 2). In this case, if we fix a tree edge $t$,
any edge that covers $t$ has one endpoint to the left of $t$ and one endpoint
to the right of $t$. We focus on 2-respecting cuts $\\{t,t^{\prime}\\}$ where
$t^{\prime}$ is on the right of $t$. We sort all the edges that cover $t$
according to their right endpoint, from the closet to the furthest from $t$.
Denote by $e_{1},...,e_{k}$ the $k$ first edges in this sorted order (in
particular, $e_{1}=t$). Let $v_{1},v_{2},...,v_{k}$ be the right endpoints of
$e_{1},...,e_{k}$, respectively. The first observation is that
$\mathsf{Cut}(t,t^{\prime})=k$ for an edge $t^{\prime}$ to the right of $t$
only if $t^{\prime}$ is on the subpath between $v_{1}$ to $v_{k}$, as
otherwise, there are more than $k$ edges:
$\\{e_{1}=t,e_{2},...,e_{k},t^{\prime}\\}$ that cross the cut defined by
$\\{t,t^{\prime}\\}$. Moreover, we can show that all the edges $t^{\prime}$ on
the subpath $S_{i}$ between $v_{i}$ to $v_{i+1}$ are in a min 2-respecting cut
with $t$ if and only if
$\mathsf{Cov}(t^{\prime})=c^{t}_{i}=\mathsf{Cov}(t)+k-2i$. The reason is as
follows. First, if $\\{t,t^{\prime}\\}$ is a min 2-respecting cut, then
$\mathsf{Cut}(t,t^{\prime})=k$ (as the minimum cut has size $k$). Second, as
explained above
$\mathsf{Cut}(t,t^{\prime})=\mathsf{Cov}(t)+\mathsf{Cov}(t^{\prime})-2\mathsf{Cov}(t,t^{\prime})$.
Finally, by the definition of the subpath $S_{i}$, we get that for all edges
$t^{\prime}\in S_{i}$, $\mathsf{Cov}(t,t^{\prime})=\mathsf{Cov}(t)-i$. The
latter follows from the fact that the edges that cover $t$ and $t^{\prime}$
are all the edges that cover $t$ expect of the $i$ edges $e_{1},...,e_{i}$.
This follows from the definition of $S_{i}$. From the above, a simple
calculation shows that $t^{\prime}\in S_{i}$ is in a min 2-respecting cut with
$t$ if and only if $\mathsf{Cov}(t^{\prime})=\mathsf{Cov}(t)+k-2i$. Hence we
can divide the path between $v_{1}$ to $v_{k}$ to $k-1$ subpaths
$S^{t}_{i}=[v_{i},v_{i+1}]$, where in each one of them the edges $t^{\prime}$
in a min 2-respecting cut with $t$ are exactly those where
$\mathsf{Cov}(t^{\prime})=c^{t}_{i}$. We can use the same argument to
represent cuts where $t^{\prime}$ is on the left of $t$. Based on these ideas,
we prove Lemma 2.3 for a path $T$.

Figure 2: Illustration of the proof of Lemma 2.3.

##### Learning the Succinct Representation.

To allow all tree edges to learn the $O(k)$ tuples
$\\{(S^{t}_{i},c^{t}_{i})\\}_{1\leq i\leq\ell}$ that represent their cuts, the
main task is to learn $O(k)$ edges that cover $t$ and are the _best_ according
to a certain criterion. To explain the idea, assume first that each tree edge
$t$ should learn only about one non-tree edge $e_{t}$, the non-tree edge that
covers $t$ and has the right endpoint closest to $t$. To do so, we can break
the tree $T$ to $O(\sqrt{n})$ subpaths of length $O(\sqrt{n})$. Let $P_{t}$ be
the subpath that contains $t$. If the edge $e_{t}$ has at least one endpoint
in $P_{t}$, then using communication inside $P_{t}$, the edge $t$ can learn
about $e_{t}$. Actually all the tree edges $t$ in $P_{t}$ can learn about
their edges $e_{t}$ in this case in $O(\sqrt{n})$ time, using the fact that
$P_{t}$ has length $O(\sqrt{n})$ and the congestion is also bounded by
$O(\sqrt{n})$ because there are just $O(\sqrt{n})$ tree edges in $P_{t}$. This
can be done in all the $O(\sqrt{n})$ subpaths of $T$ simultaneously. Another
case is that the edge $e_{t}$ does not have any endpoint in $P_{t}$. Here the
crucial observation is that the edge $e_{t}$ in this case does not depend on
the specific choice of $t$, it is an edge that covers all tree edges in
$P_{t}$ and has the right endpoint closest to $P_{t}$. There is only one such
edge for the whole subpath $P_{t}$, and we can use global communication over a
BFS tree to learn about this edge in $O(D)$ time. Since we have $O(\sqrt{n})$
subpaths $P_{t}$, then learning about the relevant edges for all subpaths
takes $O(D+\sqrt{n})$ time. Following the same ideas, all the tree edges can
learn about $O(k)$ best edges that cover them in $O(D+k\sqrt{n})$ time.
Dealing with an arbitrary tree $T$ is more challenging and will be discussed
later.

####  2.1.2 Estimating the Cost-Effectiveness via Graph Sketches

We next explain how we use the cut information learned by edges to estimate
the cost-effectiveness. To simplify the description, we first focus on a
setting that each tree edge $t$ knows the full list of min 2-respecting cuts
$\\{t,t^{\prime}\\}$ it participates in. We focus on estimating the number of
2-respecting cuts that are covered by $e$ and have exactly two tree edges;
handling 1-respecting cuts is easier.

Recall that by 2.2, a non-tree edge $e$ covers a 2-respecting cut
$\\{t,t^{\prime}\\}$ iff exactly one of $t,t^{\prime}$ is in $P_{e}$. A naive
algorithm to compute the cost-effectiveness using 2.2 could be to go over all
the tree edges $t$ in the path $P_{e}$, learn about all the min 2-respecting
cuts $\\{t,t^{\prime}\\}$ they participate in, and count in how many of them
the second edge $t^{\prime}$ in the cut is not in $P_{e}$. However, this
requires collecting a lot of information and is not efficient. We next show
how using _sketching_ ideas we can estimate the number of edges that cross the
cut. Graph sketches is a powerful tool that is used for example in
connectivity algorithms in various settings (see for example [AGM12, KKM13,
KW14, KKT15, MK21]). Many times it is used in order to find outgoing edges
from a connected component. Here the property that distinguishes between an
outgoing edge from a set $S$ and other edges is that the outgoing edges are
exactly those that have exactly one endpoint in $S$. We show that similar type
of ideas are helpful in our context. Intuitively, the reason is this: edge $e$
covers a cut $\\{t,t^{\prime}\\}$ iff exactly one of $t$ and $t^{\prime}$ is
in the path $P_{e}$. This is similar to the property that outgoing edges have
exactly one endpoint in a connected component.

##### High-level Idea.

Each tree edge $t$ uses the information about the min 2-respecting cuts
$\\{t,t^{\prime}\\}$ to compute a _sketch_ $\mathsf{Sketch}(t)$ of the min
2-respecting cuts, with the following properties.

  1. 1.

The sketch has poly-logarithmic size.

  2. 2.

Given a tree path $P$, if we look at $\oplus_{t\in P}\mathsf{Sketch}(t)$ we
can obtain a constant approximation to the number of min 2-respecting cuts
that have exactly one tree edge in $P$, with high probability. Here $\oplus$
represents the bitwise XOR of the sketches.

Given the sketches, we can obtain an efficient algorithm for approximating the
cost-effectiveness of all non-tree edges, as follows. Each non-tree edge
$e=\\{u,v\\}$ should learn $\oplus_{t\in P_{e}}\mathsf{Sketch}(t)$. This is an
aggregate function of the values $\mathsf{Sketch}(t)$ of edges in $P_{e}$.
Such computations can be done using the tool of fragment decomposition as was
shown in [Dor18]. From property 2 of the sketches and from 2.2, this gives a
constant approximation to the number of min 2-respecting cuts covered by $e$,
as needed.

##### Estimating the Cost-Effectiveness without Full Information about Minimum
Cuts.

We next explain how to extend the above algorithm to a setting where tree
edges do not know all their min 2-respecting cuts, but they have the succinct
description of min 2-respecting cuts provided by Lemma 2.3; we call this
information $\mathsf{CutInfo}(t)$. Note that for the above algorithm, tree
edges do not need to know all their min 2-respecting cuts, they just need to
be able to compute the values $\mathsf{Sketch}(t)$. Our main goal is to show
that this information can be computed efficiently.

The value $\mathsf{Sketch}(t)$ is a compressed description of all the min
2-respecting cuts $\\{t,t^{\prime}\\}$, think about it as an aggregate
function of all the values $\\{t,t^{\prime}\\}$. To be able to compute it we
need that for each cut $\\{t,t^{\prime}\\}$ either $t$ or a vertex close to
$t$ will know the name of the cut $\\{t,t^{\prime}\\}$. At a high-level, this
is obtained as follows. First note that if a vertex $v$ knows
$\mathsf{CutInfo}(t)$ and the value $\mathsf{Cov}(t^{\prime})$ for a tree edge
$t^{\prime}$ it can check if $\\{t,t^{\prime}\\}$ is min 2-respecting cut
(this just follows from the succinct description of cuts provided in Lemma
2.3). Hence if for any tree edge $t^{\prime}$ there is a vertex close by to
$t$ that knows $\mathsf{CutInfo}(t),\mathsf{Cov}(t^{\prime})$, this vertex
will know about the cut $\\{t,t^{\prime}\\}$. Our approach is to broadcast the
values $\mathsf{CutInfo}(t),\mathsf{Cov}(t)$ to $O(\sqrt{n})$ vertices close
to $t$, and additionally broadcast to the whole graph a small amount of
information. We next provide more details on our approach. First, we again
decompose the path $T$ into $O(\sqrt{n})$ subpaths of size $O(\sqrt{n})$. In
each subpath, we let all the vertices of the subpath to learn the values
$\\{\mathsf{CutInfo}(t),\mathsf{Cov}(t)\\}$ of all tree edges in the subpath.
As this is $O(k\log{n})$ bits per edge, this can be done in $O(k\sqrt{n})$
time. Now for any pair of subpaths $P_{1},P_{2}$ where there is an edge
$\\{v,v^{\prime}\\}$ between them, the vertices $v$ and $v^{\prime}$ can
exchange between them the values $\\{\mathsf{CutInfo}(t),\mathsf{Cov}(t)\\}$
of all tree edges in the subpaths $P_{1},P_{2}$. By the definition of
$\mathsf{CutInfo}(t)$, from this information $v$ and $v^{\prime}$ can deduce
the names of all cuts $\\{t,t^{\prime}\\}$ where $t\in P_{1},t^{\prime}\in
P_{2}$. Then for any edge $t\in P_{1}$, the vertex $v\in P_{1}$ can compute a
sketch of all the cuts $\\{t,t^{\prime}\\}$ it knows about. As sketches are
aggregate functions, if different vertices in the subpath $P_{1}$ know about
different cuts $\\{t,t^{\prime}\\}$ learning the value $\mathsf{Sketch}(t)$
can be done using a simple aggregate computation in the subpath. In this
description we focused on the case that there is an edge between $P_{1}$ and
$P_{2}$. The case there is no edge between them is slightly more delicate.
Here we exploit structural properties of 2-respecting cuts to show that the
min 2-respecting cuts have a very simple structure in this case, and we use a
_small amount_ of global communication to let all tree edges learn enough
information about these cuts to complete the computation of
$\mathsf{Sketch}(t)$. The full description of the algorithm appears in Section
8.

###  2.2 Estimating the Cost-Effectiveness for a General Spanning Tree $T$

Most of the ideas described above also generalize to the case that the
spanning tree $T$ is a general tree, but it requires additional ingredients
and more complex proofs. We next discuss the main ingredients needed. First,
Lemma 2.3 about the succinct representation of min cuts holds also when $T$ is
a general tree, but it requires a more involved proof. Note that when $T$ is a
path we sorted edges according to their right endpoint, and our goal is to be
able to do something similar for a general tree as well. The high-level idea
is to use an observation on the structure of 2-respecting cuts from [MN20]
that says that for each tree edge $t$, all the edges $t^{\prime}$ where
$\\{t,t^{\prime}\\}$ defines a min 2-respecting cut are on one tree path
$P_{t}$. Second, we sort the edges that cover $t$ according to the subpath
they cover in $P_{t}$ and repeat a similar proof idea to the one we used in
the case that $T$ is a path. See Section 6 for the details.

To learn the succinct cut information, the main task again is to learn $O(k)$
edges that cover $t$ and are the _best_ according to a certain criterion. Such
computations can usually be done in $\tilde{O}(D+k\sqrt{n})$ time using the
tool of _fragment decomposition_. One challenge in our case is that when $T$
is a general tree the criterion defining the best edges is specific for each
edge $t$ (as we sort the edges that cover $t$ according to a tree path
$P_{t}$). To get an efficient algorithm, we use structural properties of cuts
proved in [DEMN21] that informally speaking imply that for _many tree edges_
the paths $P_{t}$ are the same. This allows us to bound the total amount of
communication. For a more precise discussion and detailed description of the
algorithm, see Section 7.

Finally, to estimate the cost-effectiveness, we follow similar ideas to the
ones described for the path case, where instead of breaking $T$ to
$O(\sqrt{n})$ subpaths, we break the tree $T$ to $O(\sqrt{n})$ fragments of
size $O(\sqrt{n})$ and distribute the cut information inside these fragments.
As in the path case, it is easier to handle cuts $\\{t,t^{\prime}\\}$ if there
is an edge between the fragments of $t$ and $t^{\prime}$. In the case that
there is no such edge, we prove that the minimum cuts have a very special
structure and we can broadcast a small amount of information to learn about
these cuts. For full details see Section 8.

##### Conclusion.

Based on the above ideas, we obtain an $O(1)$-approximation for the cost-
effectiveness of edges in $\tilde{O}(D+k\sqrt{n})$ time. As we discuss in
Section 5, this leads to an $O(\log{k}\log{n})$-approximation for $k$-ECSS in
$\tilde{O}(k(D+k\sqrt{n}))$ time. Intuitively, the $O(\log{n})$ term in the
approximation comes from using a greedy approach to solve each one of the
connectivity augmentation problems, as we add to the solution edges with near-
optimal cost-effectiveness. The $O(\log{k})$ term comes from working in $k$
phases where we gradually augment the connectivity. The time complexity is
based on showing that if we can estimate the cost-effectiveness in
$\tilde{O}(D+k\sqrt{n})$ time, then we can augment the connectivity of $H$
from $i$ to $i+1$ in just poly-logarithmic number of iterations, where in each
one of them the cost-effectiveness is computed. Summing up over all $k$ phases
leads to $\tilde{O}(k(D+k\sqrt{n}))$ time complexity. For a detailed
discussion and a proof see Section 5.

##  3 Discussion

In this paper, we provide a randomized algorithm with a near-optimal time
complexity for the minimum cost $k$-edge-connected spanning subgraph problem
for any constant $k$. Several interesting questions remain open. First, our
algorithm obtains an $O(\log{k}\log{n})$-approximation, and a natural question
is whether it is possible to obtain a constant approximation in a similar time
complexity. While there are several centralized polynomial time algorithms
that obtain a constant approximation to the problem [GGP+94, Jai01, KV94,
CHN+22], it seems challenging to implement them efficiently in a distributed
setting (for example, a distributed implementation of the algorithm of Goemans
et al. [GGP+94] led to an $O(\log{k})$-approximation algorithm with complexity
of $O(knD)$ rounds [Sha09]). Hence, obtaining an efficient algorithm with a
constant approximation in the distributed setting seems to be a highly
challenging task that will require a new approach for the problem. Another
interesting question is whether it is possible to obtain a deterministic
algorithm with similar guarantees.

## Roadmap

The rest of the paper is organized as follows. Section 4 discusses basic tools
and claims used in our algorithm. Section 5 describes the distributed greedy
algorithm for augmenting the connectivity, that reduces the $k$-ECSS problem
to the problem of estimating cost-effectiveness. The rest of the paper focuses
on approximating the cost-effectiveness of edges. First, in Section 6, we
prove Lemma 2.3 about the succinct representation of minimum cuts. In Section
7, we show how all tree edges learn the values $\mathsf{CutInfo}(t)$ and
additional information useful for the algorithm. Finally, in Section 8, we
describe our algorithm for approximating the cost-effectiveness. Our lower
bounds appear in Appendix A.

##  4 Preliminaries

###  4.1 Cover Values and 2-respecting Cuts

Given a spanning tree $T$, we say that an edge $e=\\{u,v\\}$ _covers_ a tree
edge $t$ if $t$ in the unique tree path between $u$ and $v$. We denote by
$\mathsf{Cov}(t)$ the number of edges that cover $t$. Note that the edges that
cover $t$ are exactly the edges that cross the 1-respecting cut defined by $t$
(see Figure 3). It follows that $\mathsf{Cut}(t)=\mathsf{Cov}(t)$, where
$\mathsf{Cut}(t)$ is the size of the 1-respecting cut defined by $t$.

We next discuss 2-respecting cuts. We denote by $\mathsf{Cov}(t_{1},t_{2})$
the number of edges that cover both $t_{1}$ and $t_{2}$, and by
$\mathsf{Cut}(t_{1},t_{2})$ the value of the 2-respecting cut defined by
$t_{1},t_{2}$. The following is shown in [DEMN21], the proof is based on
showing that the edges that cross the 2-respecting cut defined by
$t_{1},t_{2}$ are exactly the edges that cover exactly one of $t_{1},t_{2}$.
See Figure 3 for illustration.

######  Claim 4.1 ([DEMN21]).

Let $t,t^{\prime}$ be tree edges, then
$\mathsf{Cut}(t,t^{\prime})=\mathsf{Cov}(t)+\mathsf{Cov}(t^{\prime})-2\mathsf{Cov}(t,t^{\prime})$.

Figure 3: The left side illustrates the 1-respecting cut defined by $t$, the
dotted edges are examples of edges that cover $t$. The right side illustrates
the 2-respecting cut defined by $t_{1},t_{2}$. The edges $e_{2},e_{3}$ are
edges that cover both $t_{1},t_{2}$, where $e_{1}$ is an edge that covers
$t_{1}$ but not $t_{2}$.

The following was shown in [Dor18].

######  Claim 4.2 ([Dor18]).

In $\tilde{O}(D+\sqrt{n})$ time, all tree edges $t$ can learn
$\mathsf{Cov}(t)$.

We next discuss a few useful observations used in our algorithm. For a non-
tree edge $e=\\{u,v\\}$, we denote by $P_{e}$ the tree path between $u$ and
$v$.

######  Claim 4.3.

A non-tree edge $e$ covers a 1-respecting cut defined by $t$ iff $t$ is in
$P_{e}$.

###### Proof.

Removing $t$ from the tree disconnects $T$ to two connected components, one is
the subtree below $t$, and the other is the rest of the tree. The edges that
cross the cut are exactly the edges that have endpoints in these two
components. Since $t$ is the only tree edge connecting these components, these
are exactly all edges where $t$ in the tree path $P_{e}$. ∎

See 2.2

###### Proof.

Note that removing the edges of a minimum cut from a graph disconnects the
graph into two connected components, we refer to them as the two sides of the
cut. Since $t,t^{\prime}$ are edges in the cut, their endpoints are on the two
different sides of the cut. If we take an edge $e=\\{u,v\\}$ that covers
exactly one of $t,t^{\prime}$, say $t$, then the path $P_{e}$ starts in the
side of the cut of $u$, and then switches to the other side when it crosses
$t$. It follows that $u$ and $v$ are on different sides of the cut, and that
$e$ is an edge that crosses the cut. Any other edge either doesn’t cover any
of $t,t^{\prime}$ or covers both of them. In the first case both $e$’s
endpoints are on the same connected component in
$T\setminus\\{t,t^{\prime}\\}$, hence they are on the same side of the cut. In
the second case, the path $P_{e}$ covered by $e$ starts on one side of the
cut, and switches sides 2 times, when crossing $t$ and $t^{\prime}$, hence
both its endpoints are on the same side of the cut. ∎

We next show that it is enough to focus on 2-respecting cuts. In a seminal
work [Kar00], Karger showed that one can find a small set of spanning trees
$T_{1},...,T_{\ell}$ of a graph $H$ such that for any minimum cut $C$ in $H$,
there is a tree $T_{j}$ in the set such that $C$ 2-respects $T_{j}$. Actually,
a stronger statement holds: cut $C$ 2-respects a _constant fraction_ of the
trees. This construction was also implemented in a distributed setting
[DHNS19, DEMN21], giving the following.222See Appendix A in [DEMN21] for a
proof. In that paper, the description of the theorem is slightly different, as
the paper focuses on finding one minimum cut, but from the lemmas that appear
before it based on [Kar00], Theorem 4.4 follows.

######  Theorem 4.4 ([Kar00, DHNS19]).

Given a graph $H$, it is possible to find a set of $\ell=\Theta(\log^{2.2}n)$
spanning trees $T_{1},T_{2},...,T_{\ell}$ such that any minimum cut in $H$
2-respects 1/3 fraction of the trees. The construction time is
$\tilde{O}(D+\sqrt{n})$ time, and the algorithm works with high probability.

This allows us to focus our attention on _min 2-respecting cuts_ , minimum
cuts that have at most 2 edges in a spanning tree $T_{j}$. In our algorithm,
to estimate the cost-effectiveness of edges, we estimate the number of min
2-respecting cuts they cover in all the spanning trees $T_{1},...,T_{\ell}$.
Using Theorem 4.4, we show the following.

######  Lemma 4.5.

[Reduction from Min Cuts to Min 2-respecting Cuts] Let $H$ be a graph with a
spanning tree $T$. Let $A$ be an $\alpha$-approximation algorithm for
computing the number of min 2-respecting cuts in $H$ covered by each edge
$e\not\in H$. If $A$ takes $S$ time and works w.h.p, then there is an
$O(\alpha)$-approximation algorithm for computing the number of minimum cuts
in $H$ covered by each edge $e\not\in H$ that takes $\tilde{O}(S+D+\sqrt{n})$
time and works w.h.p.

###### Proof.

From Theorem 4.4, it is possible to find a set $T_{1},...,T_{\ell}$ of
spanning trees with $\ell=\Theta(\log^{2.2}n)$, such that for any minimum cut
$C$ in the graph $G$, $C$ 2-respects 1/3 fraction of the spanning trees. The
construction time is $\tilde{O}(D+\sqrt{n})$ time, and the algorithm works
with high probability. By the end of the algorithm each vertex knows which
edges are adjacent to it in each one of the spanning trees.

Now we apply our $\alpha$-approximation algorithm to compute the number of min
2-respecting cuts covered by each edge $e\not\in H$ in each one of the
spanning trees $T_{1},...,T_{\ell}$. This takes $\tilde{O}(S)$ time. Denote by
$c_{i}$ the number of min 2-respecting cuts covered by $e$ in the tree
$T_{i}$, and denote by $c^{\prime}_{i}$ the estimate of $c_{i}$ returned by
the algorithm. Let $C$ be a minimum cut covered by $e$, then $C$ 2-respects at
least $1/3$ of the trees $T_{1},...,T_{\ell}$, it follows that in the sum
$c_{S}=\sum_{i=1}^{\ell}c_{i}$ each minimum cut $C$ covered by $e$ is counted
between $\ell/3$ to $\ell$ times. Also, any min 2-respecting cut is also a
minimum cut in the original graph by definition. Hence the value $3c_{S}/\ell$
gives a 3-approximation to the number of minimum cuts covered by $e$. As we
only have $\alpha$-approximations $c^{\prime}_{i}$ to the values $c_{i}$, we
can get $\alpha$-approximation to $c_{S}$ by computing
$c^{\prime}_{S}=\sum_{i=1}^{\ell}c^{\prime}_{i}$. Now taking
$3c^{\prime}_{S}/\ell$ gives a $3\alpha$-approximation to the number of
minimum cuts covered by $e$, as needed. ∎

We say that $t$ and $t^{\prime}$ are orthogonal tree edges if they are on
different root to leaf paths in the tree.

######  Claim 4.6.

Let $t$ and $t^{\prime}$ be orthogonal tree edges. Let $T_{t}$ be the subtree
of $T$ below the edge $t$. If $\\{t,t^{\prime}\\}$ is min 2-respecting cut,
then there is an edge between the subtree $T_{t}$ and the subtree
$T_{t^{\prime}}$.

###### Proof.

It is shown in [MN20, DEMN21] that if $\\{t,t^{\prime}\\}$ is a min
2-respecting cut, then there is an edge that covers both $t$ and
$t^{\prime}$.333They show something stronger, that at least half of the edges
that cover $t$ cover also $t^{\prime}$. Any edge that covers a tree edge $t$
has one endpoint in the subtree $T_{t}$, as $T_{t}$ is one of the connected
components in the 1-respecting cut defined by $t$. Hence, if there is an edge
$e$ that covers $t$ and $t^{\prime}$ and they are orthogonal, the subtrees
$T_{t}$ and $T_{t^{\prime}}$ are disjoint, and hence $e$ connects the two
subtrees. ∎

###  4.2 Fragment Decomposition

Given a spanning tree $T$, a fragment decomposition is a decomposition of the
tree into fragments with nice properties. We use the fragment decomposition
from [DEMN21], that is based on earlier constructions from [GP16, Dor18,
DG19].

In this construction, the tree is decomposed into $O(\sqrt{n})$ _edge-
disjoint_ fragments, each of size $O(\sqrt{n})$. Each fragment $F$ has a very
specific structure, it has two special vertices $r_{F}$ and $d_{F}$, that are
called the root and the unique descendant of the fragment. The fragment is
composed of one main path between $r_{F}$ and $d_{F}$, called the _highway_ of
the fragment, and additional subtrees attached to the highway. The edges on
these subtrees are called _non-highway_ edges. The only vertices in the
fragment that could be connected by a tree edge to another fragment are
$r_{F}$ and $d_{F}$, they can also be part of other fragments. Other vertices
of the fragment are internal vertices, that are not connected by a tree edge
to any other fragment. See Figure 4 for illustration.

The structure of the fragments is captured by a _skeleton tree_. In this tree
the vertices correspond to all vertices that are either $r_{F}$ or $d_{F}$ in
at least one fragment, and the edges correspond to the highways of the
fragments. As there are $O(\sqrt{n})$ fragments, the description of the tree
has $O(\sqrt{n})$ size, and we can broadcast it to the whole graph in
$O(D+\sqrt{n})$ time. The construction of the fragment decomposition takes
$\tilde{O}(D+\sqrt{n})$ time.

Figure 4: Illustration of the fragment decomposition.

######  Theorem 4.7 ([DEMN21]).

Given a spanning tree $T$, the fragment decomposition can be computed in
$\tilde{O}(D+\sqrt{n})$ time. By the end of the computation, all vertices know
their fragment, and the complete structure of the skeleton tree.

One useful property of the fragment decomposition is that it allows non-tree
edges to compute aggregate functions of tree edges that they cover
efficiently. For a proof see Claim 2.5 in [Dor20].444The proof focuses on the
case that the information $m_{t}$ of tree edges is of size $O(\log{n})$, if
the size is poly-logarithmic, the same proof idea works and it adds a poly-
logarithmic term to the time complexity. Similar proof for special cases
appears in [Dor18].

######  Claim 4.8 ([Dor20]).

Assume that each tree edge $t$ has an information $m_{t}$ of poly-logarithmic
size. In $\tilde{O}(D+\sqrt{n})$ time, all the non-tree edges $e$ can learn an
aggregate function of the values $\\{m_{t}\\}_{t\in P_{e}}$.

We next discuss a few simple observations on the fragment decomposition used
in our algorithm.

######  Claim 4.9.

Let $e$ be an edge where both its endpoints are not internal vertices in the
fragment $F$ (they can be either outside the fragment, or the root or unique
descendant of the fragment), then $e$ either covers exactly all tree edges in
the highway $h_{F}$ of $F$, or does not cover any edge of $F$.

###### Proof.

Since both the endpoints of $e$ are not internal vertices in $F$, then the
tree path covered by $e$ either does not go through $F$, or enters and leaves
$F$ using the vertices $r_{F}$ and $d_{F}$ that are the only ones connected to
vertices outside $F$, in this case $e$ covers exactly the highway of $F$. ∎

We denote by $LCA(u,v)$ the lowest common ancestor of $u$ and $v$. The
following claim follows from the structure of the fragment decomposition.

######  Claim 4.10.

Let $u,v$ be two vertices that are not internal vertices in the fragment $F$
(they can either be outside the fragment, or the root or descendant of $F$),
then $LCA(u,v)$ is not an internal vertex in $F$.

###  4.3 LCA Labels

Given a spanning tree $T$, the tool of lowest common ancestor (LCA) labels
allows to give the vertices of the graph small labels of size $O(\log{n})$
bits such that given the labels of two vertices $u$ and $v$ we can infer the
label of $LCA(u,v)$ directly from their labels. During our algorithm LCA
labels will be useful for many tasks, such as checking if an edge $e$ covers a
tree edge $t$, and checking if a vertex $w$ is inside the tree path between
$u$ and $v$. When we work with a specific tree $T$, we use the LCA labels as
the unique ids of vertices, and usually assume that if a vertex $v$ learns
about a vertex $u$ it learns the LCA label of $u$.

We use the construction from [CHD20, Dor20] (see Lemma 2.9 in [Dor20]). This
construction uses the fragment decomposition discussed above as one of its
ingredients, and for each vertex the id of its fragment is part of its LCA
label, we will exploit this property in our algorithm.

######  Lemma 4.11 ([CHD20]).

In $O(D+\sqrt{n}\log^{*}{n})$ rounds, we can assign the vertices of a tree $T$
labels of size $O(\log{n})$, such that given the labels of two vertices $u$
and $v$, we can infer the label of their LCA.

The following useful property is shown in [CHD20].

######  Claim 4.12 ([CHD20]).

Given the LCA labels of a tree edge $t$, and an edge $e$, one can deduce if
$e$ covers $t$.

###  4.4 Basic Notation and Tools

Given a spanning tree $T$, we denote by $p(u)$ the parent of $u$ in the tree.
We say that two vertices $u$ and $v$ in the tree are _orthogonal_ if they are
on different tree paths, i.e., if $u$ is not an ancestor of $v$ and vice
verse.

During our algorithm, we sometimes broadcast information in a spanning tree
$T$. For example, in the subtrees of the fragments decomposition or in a
global BFS tree. Broadcasting $\ell$ pieces of information can be easily done
in $O(h+\ell)$ time, where $h$ is the height of the tree (see for example
[Pel00]).

######  Claim 4.13.

Assume that there are $\ell$ pieces of information of $O(\log{n})$ bits that
are initially distributed between a subset of vertices in a tree $T$ of height
$h$. In $O(h+\ell)$ time all vertices in the tree can learn all $\ell$ pieces
of information.

For example, if we use a BFS tree we get a complexity of $O(D+\ell)$ time. We
assume in the algorithm that we have a global BFS tree, such a tree can be
constructed in $O(D)$ time [Pel00].

##  5 Distributed Greedy Algorithm for Connectivity Augmentation

In this section, we discuss the distributed greedy algorithm for augmenting
the connectivity. We prove that if we can estimate the cost-effectiveness of
edges in $\tilde{O}(D+k\sqrt{n})$ time, we get an
$O(\log{k}\log{n})$-approximation for $k$-ECSS in $\tilde{O}(k(D+k\sqrt{n}))$
time. The algorithm generally follows the framework in [Dor18]. There are
slight changes since in our case we approximate the cost-effectiveness where
in [Dor18] it is computed exactly. We also prove that the approach from
[Dor18] actually leads to an $O(\log{k}\log{n})$-approximation for $k$-ECSS,
improving the $O(k\log{n})$-approximation guarantee shown in [Dor18].

To find a low-cost $k$-edge-connected spanning subgraph of a graph $G$, we
work in iterations, where in iteration $i$ we are given an $(i-1)$-edge-
connected spanning subgraph $H_{i-1}$ of $G$ and we augment it to be $i$-edge-
connected by adding a low-cost set of edges from $G$ to $H_{i-1}$. For
example, in the first iteration $H_{0}=\emptyset$ and we can compute a minimum
spanning tree $H_{1}$ to solve the problem. In general, in iteration $i$, our
goal is to solve the following augmentation problem we call $Aug_{i}$.

######  Definition 5.1 (Augmentation Problem).

In the augmentation problem $Aug_{i}$ we are given an $i$-edge-connected graph
$G=(V,E)$ and an $(i-1)$-edge-connected spanning subgraph $H_{i-1}$ of $G$.
The goal is to find a minimum cost set of edges $A\subseteq E$ such that
$H_{i}=H_{i-1}\cup A$ is $i$-edge-connected.

An $\alpha$-approximation to $Aug_{i}$ is a set of edges $A$ such that
$H_{i-1}\cup A$ is $i$-edge-connected, and $w(A)\leq\alpha w(A^{*})$, where
$A^{*}$ is an optimal augmentation. It is easy to see that if we can get an
$\alpha$-approximation solution to $Aug_{i}$ for all $i$, then we get a
$(k\alpha)$-approximation to $k$-ECSS, as the optimal solution $H^{*}$ for
$k$-ECSS can be used to augment any subgraph $H$ to be $k$-edge-connected.
This implies that $w(A^{*}_{i})\leq w(H^{*})$ for any $i$, where $A^{*}_{i}$
is the optimal solution for $Aug_{i}$. Using a tighter analysis, we can show
that the achieved approximation for $k$-ECSS is in fact $(\alpha\log{k})$.
Hence, our main goal is to approximate $Aug_{i}$.

##### Solving the Augmentation Problem via a Set Cover Algorithm.

The problem $Aug_{i}$ can be seen as a special case of the set cover problem,
where our goal is to cover cuts of size $i-1$ in $H_{i-1}$. Concretely, as
$H_{i-1}$ is $(i-1)$-edge-connected, the minimum cut size in $H_{i-1}$ is at
least $i-1$. To augment the connectivity of $H_{i-1}$ to $i$ our goal is to
add edges that cover all cuts that have size $i-1$ in $H_{i-1}$, where an edge
$e\not\in H_{i-1}$ _covers_ a cut $C$ if $(H_{i-1}\setminus C)\cup\\{e\\}$ is
connected.

##### Centralized Algorithm for this Special Set Cover Problem.

A simple centralized $O(\log{n})$-approximation for $Aug_{i}$ can be obtained
using the simple greedy algorithm for set cover, comparing edges according to
the number of cuts they cover. Let us elaborate. We denote by $C_{e}$ the set
of cuts of size $i-1$ in $H_{i-1}$ covered by the edge $e\not\in H_{i-1}$. We
define the cost-effectiveness of an edge $e\not\in{H_{i-1}}$ to be
$\frac{|C_{e}|}{w(e)}$ where $w(e)$ is the weight of $e$. Intuitively our goal
is to add edges with high values of cost-effectiveness to the augmentation,
because that allows to cover many cuts while paying a low cost. This is indeed
the idea of the centralized greedy algorithm. In this algorithm, at each step,
we add an edge with maximum cost-effectiveness to the augmentation $A$, and we
continue until $H_{i-1}\cup A$ is $i$-edge-connected.

##### Distributed Algorithms for this Special Set Cover Problem.

To implement this approach in a distributed setting we follow the approach in
[Dor18], based on a distributed set cover algorithm. At a high-level, all
edges with near-maximal cost-effectiveness values are considered as
_candidates_ to be added to the augmentation, and the algorithm uses
randomization to choose which ones of them to add, such that many cuts are
covered, but we do not add many edges to cover the same cuts. The whole
algorithm requires only poly-logarithmic number of iterations to terminate,
where in each iteration the cost-effectiveness of edges should be computed. We
next discuss the algorithm in detail.

###  5.1 The Algorithm for $Aug_{k}$

Recall that the input to $Aug_{k}$ is a $k$-edge-connected graph $G$, and
$(k-1)$-edge-connected subgraph $H$ of $G$, and our goal is to find a low-cost
set of edges $A$ from $G$ such that $H\cup A$ is $k$-edge-connected. During
the algorithm we maintain an augmentation $A$ where initially $A=\emptyset$.
In the greedy algorithm, the candidates to be added to $A$ are edges with
near-maximal cost-effectiveness, where the cost-effectiveness $\rho(e)$ of an
edge $e$ is equal to $\frac{|C_{e}|}{w(e)}$ where $C_{e}$ is the set of cuts
of size $k-1$ in $H\cup A$ covered by $e$.

Our algorithm is composed of $O(\log{n})$ _epochs_ , where in epoch $i$ we
handle edges with cost-effectiveness about $M/2^{i}$, where $M$ is the maximum
possible value for cost-effectiveness. We assume for simplicity that the
weights are positive integers polynomial in $n$.555Dealing with zero-weight
edges is easy, as we can add all of them to $A$ without increasing the cost of
the solution. Since the number of minimum cuts in a graph is at most
$O(n^{2})$ and the minimum weight is 1, we have that $M=O(n^{2})$. We denote
by $w_{max}$ the maximum weight. During epoch $i$ edges with cost-
effectiveness about $M/2^{i}$ are considered as _candidates_ to be added to
the augmentation. When the epoch ends the maximum cost-effectiveness value
decreases by a constant factor.

Each epoch is composed of $O(\log{n})$ _phases_ , where in phase $j$ our goal
is to handle cuts that are covered by about $m/2^{j}$ candidates. We denote by
$deg(C)$ the number of candidates that cover a cut $C$. By the end of phase
$j$ all the cuts of degree about $m/2^{j}$ are covered, and the maximum degree
$deg(C)$ decreases by a constant factor.

To get a good approximation, we want to guarantee two properties. First, that
the candidates are only edges with near-optimal cost-effectiveness. This is
important to get the $O(\log{n})$-approximation guarantee of the greedy
centralized algorithm. Second, that we do not add too many candidates to cover
the same cuts. Note that in the centralized algorithm, only one edge is added
to the augmentation at each time, and ideally we want to make sure that also
in our case at most $O(1)$ candidates are added to cover each cut. To obtain
this, we work as follows. Recall that in phase $j$, $deg(C)\leq m/2^{j}$. Note
that since there are $deg(C)$ candidates that cover $C$, if we add each one of
them to the augmentation with probability $1/deg(C)$, in expectation we add
one candidate to cover $C$. Hence, to cover cuts of degree about $m/2^{j}$, we
add candidates to the augmentation with probability $2^{j}/m$. To guarantee
that all these cuts are indeed covered with high probability we repeat the
process $O(\log{n})$ times. It is important to note that for the algorithm to
work we do not need to know the degrees of cuts (that seem difficult to
compute). However, the algorithm guarantees that we cover all cuts of degree
about $m/2^{j}$, even if we do not know their identity. The algorithm is
summarized in Algorithm 1. The value $c$ is a constant that depends on the
analysis. One small technical detail is that our algorithm for approximating
cost-effectiveness assumes that the minimum cut in the graph $H\cup A$ is
indeed $k-1$ and not larger. To make sure that this is the case, we terminate
the algorithm in the first iteration that $H\cup A$ is $k$-edge-connected, we
can check this using the exact min cut algorithm in [DEMN21].

Algorithm 1 Greedy Distributed Algorithm for $Aug_{k}$.

1:Input: a $k$-edge-connected graph $G$ and a $(k-1)$-edge-connected spanning
subgraph $H$ of $G$.

2:Output: a set of edges $A$ such that $H\cup A$ is $k$-edge-connected.

3:$A\leftarrow\emptyset$

4:for $i=1,...,\log{(Mw_{max})}$ do

5: If $H\cup A$ is $k$-edge-connected, terminate

6: For each edge $e\not\in H\cup A$, compute $\alpha$-approximation
$\rho^{\prime}(e)$ of $\rho(e)$

7: Define $Candidates_{i}$ to be the set of edges $e$ where
$\rho^{\prime}(e)\geq\frac{M}{\alpha 2^{i}}$

8: for $j=0,...,\log{m}$ do

9: for $\ell=1,...,c\log{n}$ do

10: If $H\cup A$ is $k$-edge-connected, terminate

11: For each edge $e\in Candidates_{i}\setminus A$, compute
$\alpha$-approximation $\rho^{\prime}(e)$ of $\rho(e)$

12: Remove $e$ from $Candidates_{i}$ if $\rho^{\prime}(e)<\frac{M}{\alpha
2^{i}}$ or if $e\in A$

13: Each $e\in Candidates_{i}$ is added to $A$ with probability $2^{j}/m$

14: end for

15: end for

16:end for

###  5.2 Analysis

We start with simple observations on Algorithm 1.

######  Claim 5.2.

By the end of epoch $i$, the maximum cost-effectiveness of an edge $e\not\in
H\cup A$ is smaller than $M/2^{i}$.

###### Proof.

First note that the cost-effectiveness of an edge can only decrease during the
algorithm, as cuts of size $k-1$ in $H\cup A$ covered by $e$ can be covered
when we add edges to $A$. Let $e$ be an edge that has cost-effectiveness at
least $M/2^{i}$ at the beginning of epoch $i$, and that is not added to $A$ in
epoch $i$ or before it. As long as $\rho(e)\geq M/2^{i}$, then
$\rho^{\prime}(e)\geq\frac{M}{\alpha 2^{i}}$, as $\rho^{\prime}(e)$ is an
$\alpha$-approximation to $\rho(e)$. This means that $e\in Candidates_{i}$ as
long as $\rho(e)\geq M/2^{i}$. In particular, if $\rho(e)\geq M/2^{i}$ in
phase $j=\log{m}$, then $e$ is added to $A$ with probability 1, a
contradiction. Hence, the cost-effectiveness of $e$ decreases until the end of
the phase. ∎

######  Claim 5.3.

By the end of the algorithm, $H\cup A$ is $k$-edge-connected.

###### Proof.

From Claim 5.2, after the last phase, the maximum cost-effectiveness of
$e\not\in H\cup A$ is smaller than $1/w_{max}$. This means that $\rho(e)=0$
for all edges not in $H\cup A$. This implies that all cuts of size $k-1$ are
covered. If $C$ is a cut of size $k-1$ in $H$, since $G$ is $k$-edge-connected
there is at least one edge $e\not\in H$ that covers the cut. As long as $C$ is
not covered, $\rho(e)\geq 1/w_{max}$. By the end of the algorithm either $e\in
A$ or $\rho(e)=0$, in both cases $C$ is covered. ∎

We next analyze the approximation ratio of the algorithm. The analysis
generally follows [Dor18] with slight changes. For the analysis we assign
costs to cuts of size $k-1$ in $H$ according to the epoch they are covered in.
For a cut $C$ of size $k-1$ in $H$, that is first covered in epoch $i$, we
define $cost(C)=2^{i}/M$. The proof is based on showing that $w(A)\approx
O(\alpha^{2})\sum_{C}cost(C)\leq O(\alpha^{2}\log{n})w(A^{*})$, where $w(A)$
is the weight of the augmentation $A$ and $A^{*}$ is an optimal augmentation.
The proof follows [Dor18] with the following changes. First, we adapt the
proof to the case that we only have approximations to the cost-effectiveness
(this adds $O(\alpha^{2})$ term to the approximation obtained). Second, we
compare the solution to an optimal _fractional_ solution. While this does not
affect the approximation we obtain for $Aug_{k}$, it allows us later to show
that the final approximation obtained for $k$-ECSS is $O(\log{k}\log{n})$,
improving the $O(k\log{n})$ guarantee shown in [Dor18]. We start by discussing
the proof of the right inequality.

We say that $A^{\prime}$ is a fractional solution for $Aug_{k}$ if
$A^{\prime}$ assigns values $x(e)\geq 0$ to all edges, such that the following
holds. If $C$ is a cut of size $k-1$ in $H$, and $E_{C}$ are the edges in
$G\setminus H$ that cover $C$ we have $\sum_{e\in E_{C}}x(e)\geq 1$ (this is
analogous to the requirement that all cuts are covered). An optimal fractional
solution is a solution that minimizes $\sum_{e\not\in H}w(e)x(e)$. For a
fractional solution $A^{\prime}$, we define $w(A^{\prime})=\sum_{e\not\in
H}w(e)x(e)$, where $x(e)$ are the values given by the solution $A^{\prime}$.
We prove the following. The proof is based on the classical analysis of the
greedy set cover algorithm, and is deferred to Appendix B.

######  Claim 5.4.

$\sum_{C}cost(C)\leq O(\log{n})w(A^{*})$, where $A^{*}$ is an optimal
fractional solution to $Aug_{k}$.

The next claim follows from [Dor18], the main difference in our case is the
extra $O(\alpha^{2})$ term that comes from the fact we approximate the cost-
effectiveness, and not compute it exactly. See Appendix B for details.

######  Claim 5.5.

$E[w(A)]=O(\alpha^{2})E[\sum_{C}cost(C)].$

From Claims 5.4 and 5.5 we get that $E[w(A)]=O(\alpha^{2}\log{n})w(A^{*}).$
This gives approximation of $O(\alpha^{2}\log{n})$ in expectation to
$Aug_{k}$. We next show that this leads to an approximation of
$O(\alpha^{2}\log{k}\log{n})$ to $k$-ECSS. Note the our algorithm for
$Aug_{k}$ has $O(\log^{3}{n})$ iterations where in each iteration the only
complex computation is checking if a graph is $k$-edge-connected and
approximating the cost-effectiveness of edges. The first task can be solved in
$\tilde{O}(D+\sqrt{n})$ time using the exact min cut algorithm in [DEMN21]. In
later sections we show that we get an $O(1)$-approximation of the cost-
effectiveness of all edges in $\tilde{O}(D+k\sqrt{n})$ time. Based on this, we
get the following.

######  Theorem 5.6.

Assume that there is an $O(1)$-approximation algorithm for computing the cost-
effectiveness of edges that takes $\tilde{O}(D+i\sqrt{n})$ time where $i$ is
the the size of the minimum cut in the graph $H$ we augment. Then there is an
$O(\log{k}\log{n})$-approximation algorithm for $k$-ECSS that runs in
$\tilde{O}(k(D+k\sqrt{n}))$ time. The algorithm works with high probability.

###### Proof.

To solve $k$-ECSS we start with an empty subgraph $H$. To augment its
connectivity to 1 we build an MST $T^{*}$. Next, we work in iterations
$i=2,...,k$, where in iteration $i$ we augment the connectivity of $H$ from
$i-1$ to $i$ using our $O(\log{n})$-approximation for $Aug_{i}$. Our final
graph $H$ is $k$-edge-connected (assuming that the original input graph is
$k$-edge-connected), and the time complexity is $\tilde{O}(k(D+k\sqrt{n}))$,
as solving $Aug_{i}$ takes $\tilde{O}(D+i\sqrt{n})$ time, as it requires
$O(\log^{3}{n})$ iterations where in each one we approximate the cost-
effectiveness in $\tilde{O}(D+i\sqrt{n})$ time, and also compute the min cut
in the graph $H\cup A$ in $\tilde{O}(D+\sqrt{n})$ time using the algorithm in
[DEMN21].

We next analyze the approximation ratio obtained. We denote by $H_{i-1}$ the
graph $H$ at the beginning of iteration $i$. Let $H^{*}$ be a minimum-cost
$k$-edge-connected spanning subgraph. First, $w(T^{*})\leq w(H^{*})$, where
$T^{*}$ is the minimum spanning tree of the graph, as $H^{*}$ is a spanning
subgraph. Denote by $A_{i}$ the set of edges we add to $H$ in iteration $i$.
Recall that $E[w(A_{i})]\leq O(\log{n})w(A^{*})$, where $A^{*}$ is an optimal
fractional solution to $Aug_{i}$ with the input graph $H_{i-1}$. We show that
there is a fractional solution $A^{\prime}_{i}$ to $Aug_{i}$ of cost at most
$\frac{1}{k-(i-1)}w(H^{*})$. The fractional solution is defined as follows.
For any edge $e\in H^{*}\setminus H_{i-1}$, we set $x(e)=\frac{1}{k-(i-1)}$.
For all other edges $x(e)=0$. The cost of the solution is clearly at most
$\frac{1}{k-(i-1)}w(H^{*})$. We next show that this is a valid fractional
solution. Let $C$ be a cut of size $i-1$ in $H_{i-1}$. We need to show that
$\sum_{e\in E_{C}}x(e)\geq 1$. Since $C$ is a minimum cut in $H_{i-1}$,
removing the edges of $C$ from $H_{i-1}$ splits it to two connected components
$U,V\setminus U$. Since $H^{*}$ is $k$-edge-connected there are at least $k$
edges in $H^{*}$ between $U$ and $V\setminus U$. Moreover, as $C$ is a cut of
size $i-1$ in $H_{i-1}$, at most $i-1$ of these edges are in $H_{i-1}$. Hence,
there are at least $k-(i-1)$ edges that cover $C$ in $H^{*}\setminus H_{i-1}$.
Since for each of these edges we have $x(e)=\frac{1}{k-(i-1)}$, we get that
$\sum_{e\in E_{C}}x(e)\geq 1$ as needed. This gives $E[w(A_{i})]\leq O(\log
n)\frac{1}{k-(i-1)}w(H^{*})$. If we sum over all iterations, we get that

$E[w(H)]\leq
w(T^{*})+O(\log{n})\sum_{i=2}^{k}\frac{1}{k-(i-1)}w(H^{*})=O(\log{k}\log{n})w(H^{*}).$

This provides $O(\log{k}\log{n})$-approximation in expectation. To get the
approximation guarantee w.h.p we can just repeat the algorithm $O(\log{n})$
times and take the lowest cost solution obtained. Note that in $O(D)$ time we
can learn the cost of the solution by an aggregate computation in a BFS tree.
This completes the proof. ∎

##  6 Succinct Representation of Min Cuts

A key ingredient of our algorithm is a structural lemma that shows that for
each tree edge $t$, we can store $O(k\log{n})$ bits that represent all the min
2-respecting cuts containing $t$. In more detail, if we fix an edge $t$, all
the edges $t^{\prime}$ such that $\mathsf{Cut}(t,t^{\prime})=k$ can be divided
to $\ell=O(k)$ segments $S^{t}_{1},...,S^{t}_{\ell}$ with corresponding cover
values $c^{t}_{1},...,c^{t}_{\ell}$ such that the edges in $S^{t}_{i}$ where
$\mathsf{Cut}(t,t^{\prime})=k$ are exactly all edges in $S^{t}_{i}$ where
$\mathsf{Cov}(t^{\prime})=c^{t}_{i}$.

See 2.3

To simplify the presentation, we first give a proof for the case that $T$ is a
path, and later show how to extend the proof to a general tree.

###### Proof for a path $T$..

Fix a tree edge $t$. For the proof it is convenient to give an orientation to
the path $T$ and focus first on min cuts $\\{t,t^{\prime}\\}$ where
$t^{\prime}$ is on the right of $t$. We look at all edges that cover $t$, each
such edge has one endpoint to the left of $t$ and one endpoint to the right of
$t$, we sort these edges according to the right endpoint, from the closest to
the furthest from $t$. Let $e_{1},...,e_{k}$ be the first $k$ edges according
to this order, and let $v_{1},...,v_{k}$ be the corresponding right endpoints
of $e_{1},...,e_{k}$. See Figure 5 for illustration. Note that any edge
$t^{\prime}$ to the right of $v_{k}$ cannot be in a min 2-respecting cut with
$t$, as there are more than $k$ edges crossing the cut defined by
$\\{t,t^{\prime}\\}$: the edges $e_{1},...,e_{k}$ that cover $t$ and not
$t^{\prime}$, and the edge $t^{\prime}$ that covers $t^{\prime}$ and not $t$.
Also, note that there are indeed at least $k$ edges that cover $t$ as
$\mathsf{Cov}(t)\geq k$ because the min cut has size $k$. For $1\leq i\leq
k-1$, we define $S^{t}_{i}$ to be the segment in $T$ between $v_{i}$ to
$v_{i+1}$. As $t$ is also an edge that covers $t$, the vertex $v_{1}$ is the
right endpoint of $t$. Also, it may be the case that some segments are empty
in the case there are multiple edges that cover $t$ and have the same right
endpoint. We define $c^{t}_{i}=\mathsf{Cov}(t)+k-2i$.

We next show that the tuples $(S^{t}_{i},c^{t}_{i})$ capture all the min
2-respecting cuts of the form $\\{t,t^{\prime}\\}$ where $t^{\prime}$ is on
the right of $t$. As explained above, all edges $t^{\prime}$ in a min
2-respecting cut with $t$ are inside the segment between $v_{1}$ to $v_{k}$,
hence they are contained in one of the segments $S^{t}_{i}$. Let $t^{\prime}$
be an edge in $S^{t}_{i}$, we show that $\mathsf{Cut}(t,t^{\prime})=k$ iff
$\mathsf{Cov}(t^{\prime})=c^{t}_{i}$. Recall that by Claim 4.1,
$\mathsf{Cut}(t,t^{\prime})=\mathsf{Cov}(t)+\mathsf{Cov}(t^{\prime})-2\mathsf{Cov}(t,t^{\prime})$.
Now by the definition of the sets $S^{t}_{i}$, any edge $t^{\prime}$ inside
$S^{t}_{i}$ is covered by all edges that cover $t$ except $e_{1},...,e_{i}$
that have their right endpoint before $S^{t}_{i}$. This follows as any edge
that covers $t$ has one endpoint on the left of $t$ and one endpoint on the
right of $t$, hence it covers $t^{\prime}$ iff this right endpoint is on the
right of $t^{\prime}$. Hence, by definition
$\mathsf{Cov}(t,t^{\prime})=\mathsf{Cov}(t)-i$ for all edges in $S^{t}_{i}$.
If $\mathsf{Cut}(t,t^{\prime})=k$, we have that
$k=\mathsf{Cov}(t)+\mathsf{Cov}(t^{\prime})-2\mathsf{Cov}(t,t^{\prime})=\mathsf{Cov}(t)+\mathsf{Cov}(t^{\prime})-2(\mathsf{Cov}(t)-i)$.
This gives $\mathsf{Cov}(t^{\prime})=\mathsf{Cov}(t)+k-2i=c^{t}_{i}$, as
needed.

This completes the proof for cuts of the right of $t$, to handle cuts where
$t^{\prime}$ is on left of $t$ we can repeat the same arguments where we
replace right by left. Overall we get $2(k-1)=O(k)$ tuples
$(S^{t}_{i},c^{t}_{i})$ that capture all the min 2-respecting cuts that
contain $t$. ∎

Figure 5: Illustration of the proof of Lemma 2.3. A tree edge $t^{\prime}\in
S_{i}$ is in a min 2-respecting cut with $t$ iff
$\mathsf{Cov}(t^{\prime})=c^{t}_{i}=\mathsf{Cov}(t)+k-2i$.

###  6.1 A Proof for a General Tree

We next generalize the proof to a general tree $T$. There are two main
ingredients. First, we use structural properties of cuts shown in [MN20,
DEMN21] to focus our attention only on one tree path $P_{t}$ per edge $t$.
Second, while now non-tree edges that cover $t$ may have endpoints outside
$P_{t}$, we show that we can compare them and sort them according to the
subpath of $P_{t}$ they cover. This allows us to follow the main proof idea of
the path case also when dealing with a general tree. We next discuss this in
detail. First, we use the following.

######  Lemma 6.1.

[MN20] Let $G$ be a graph with minimum cut of size $k$, and let $T$ be a
spanning tree of $G$. For each tree edge $t$, all the edges
$\\{t^{\prime}|\mathsf{Cut}(t,t^{\prime})=k\\}$ are in one tree path $P_{t}$
containing $t$.

The proof follows from [MN20], we add a proof in Appendix C for completeness.

##### Comparing edges.

In the path case we compared different edges that cover $t$ according to their
right endpoint. Ideally, we want to follow a similar argument now with respect
to the path $P_{t}$. However, the edges that cover $t$ can have their
endpoints outside $P_{t}$. To deal with it, we compare edges according to the
subpath they cover in $P_{t}$. For doing so, we need the following
definitions.

Let $t=\\{u,p(u)\\}$ be a tree edge, and let $P$ be a tree path where $t\in
P$. Let $e$ be an edge that covers $t$. We next define two virtual endpoints
$v_{h}(e,P),v_{l}(e,P)$ in $P$ such that $e$ covers exactly the subpath of $P$
between $v_{l}(e,P)$ and $v_{h}(e,P)$. To do so, we first take a closer look
at $P$. The path $P$ has one part below $u$ and one part that starts above
$p(u)$ and ends either above $p(u)$ or orthogonal to $p(u)$. We call these
parts $P^{l}$ and $P^{h}$ respectively. Let $\\{p_{l},p_{h}\\}$ be the
endpoints of $P$ where $p_{l}$ is the endpoint below $u$. Similarly, let
$\\{v_{l},v_{h}\\}$ be the endpoints of $e$ where $v_{l}$ is the endpoint
below $u$ (as $e$ is an edge that covers $t$ it has one such endpoint).

We define $v_{l}(e,P)=LCA(p_{l},v_{l})$, since $u$ is an ancestor of both
$p_{l}$ and $v_{l}$, $v_{l}(e,P)$ is a vertex in $P$. The definition of
$v_{h}(e,P)$ requires two steps. First, let $a_{e}=LCA(p(u),v_{h})$ and
$a_{P}=LCA(p(u),p_{h})$. If $a_{e}\neq a_{P}$, and $a_{e}$ is below $a_{P}$,
we define $v_{h}(e,P)=a_{e}$. If $a_{e}\neq a_{P}$, and $a_{P}$ is below
$a_{e}$, we define $v_{h}(e,P)=a_{P}$. Otherwise, $a_{e}=a_{P}$, and we define
$v_{h}(e,P)=LCA(p_{h},v_{h})$. See Figure 6 for illustration.

######  Claim 6.2.

The tree path between $v_{l}(e,P)$ and $v_{h}(e,P)$ is exactly the subpath of
$P$ covered by $e$. Moreover, the subpath between $v_{l}(e,P)$ to $u$ is the
subpath of $P^{l}$ covered by $e$, and the subpath between $p(u)$ to
$v_{h}(e,P)$ is the subpath of $P^{h}$ covered by $e$.

Figure 6: The path $P$ is the bold path between $p_{l}$ to $p_{h}$. On the
right there are illustrations of several edges $e$ and the corresponding
endpoints $v_{l}(e,P),v_{h}(e,P)$.

###### Proof.

The edge $e=\\{v_{l},v_{h}\\}$ covers $t=\\{u,p(u)\\}$ and the tree paths
$P_{1},P_{2}$ between $v_{l}$ to $u$ and between $p(u)$ to $v_{h}$,
respectively. We next show that the intersection of $P_{1},P_{2}$ with $P$ is
exactly captured by the vertices $v_{l}(e,P)$ and $v_{h}(e,P)$.

First, $P_{1}$ and $P^{l}$ are two subpaths below $t$ that start at $u$, they
may have some joint edges before they diverge to two different subpaths that
end at $v_{l}$ and $p_{l}$, the point they diverge is exactly
$LCA(v_{l},p_{l})=v_{l}(e,P)$. Hence, $e$ covers exactly the subpath of
$P^{l}$ between $v_{l}(e,P)$ and $u$.

The paths $P^{h}$ and $P_{2}$ are both paths that start above $p(u)$ and have
one part above $p(u)$ and one orthogonal to $p(u)$. More concretely, $P^{h}$
is the path between $p(u)$ and $p_{h}$. It has one part between $p(u)$ and
$LCA(p(u),p_{h})=a_{P}$ and the second part between $a_{P}$ and $p_{h}$.
Similarly, the path $P_{2}$ has one part between $p(u)$ and
$LCA(p(u),v_{h})=a_{e}$ and the second part between $a_{e}$ and $v_{h}$. If
$a_{e}\neq a_{P}$ then the second parts of the two paths are disjoint, and the
intersection of the first parts is all edges above $p(u)$ that are below
$a_{e}$ and $a_{P}$. By the definition of $v_{h}(e,P)$ this is exactly the
subpath between $p(u)$ and $v_{h}(e,P)$. If $a_{e}=a_{P}$, then the first
parts of the two paths are equal, and they may have some joint edges below
$a_{P}$, until they diverge to two subpaths that end at $p_{h}$ and $v_{h}$.
The point they diverge is exactly $LCA(p_{h},v_{h})$, which is some vertex in
the subtree rooted at $a_{P}=a_{e}$, as this is an ancestor of both vertices.
By definition, $v_{h}(e,P)=LCA(p_{h},v_{h})$ in the case that $a_{e}=a_{P}$,
and indeed $e$ covers exactly the subpath of $P^{h}$ between $p(u)$ to
$v_{h}(e,P)$. This path has two parts, one from $p(u)$ to $a_{P}$, and the
second from $a_{P}$ to $v_{h}(e,P)$. ∎

From the definition of $v_{l}(e,P),v_{h}(e,P)$, we can compute them using LCA
computations. Note that LCA computations can also allow checking which
endpoint of a path $P$ or an edge $e$ is below $t$, or check if two vertices
are in the same tree path (in which case one is ancestor of the other), and if
so determine which one of them is higher in the tree.

######  Claim 6.3.

Given the LCA labels of the endpoints $\\{p_{l},p_{h}\\}$ of a path $P$ that
contains the tree edge $t=\\{u,p(u)\\}$, the LCA labels of the endpoints
$\\{v_{l},v_{h}\\}$ of an edge $e$ that covers the tree edge $t$, and the LCA
labels of $\\{u,p(u)\\}$ one can deduce the LCA labels of the vertices
$v_{l}(e,P),v_{h}(e,P)$.

We can now give a proof for Lemma 2.3 where $T$ is a general tree.

###### Proof of Lemma 2.3.

Fix a tree edge $t=\\{u,p(u)\\}$. From Lemma 6.1, all the edges where
$\mathsf{Cut}(t,t^{\prime})=k$ are in one tree path $P_{t}$ containing $t$.
This path has one subpath $P_{t}^{l}$ below $t$ starting at $u$, and another
subpath $P_{t}^{h}$ starting at $p(u)$. We first focus on edges $t^{\prime}$
in the first subpath $P_{t}^{l}$. We look at all edges that cover $t$ and
compare them according to the subpath they cover in $P_{t}^{l}$. From Claim
6.2, we know that an edge $e$ that covers $t$, covers exactly the subpath of
$P_{t}^{l}$ between $v_{l}(e,P_{t})$ and $u$. Note that all vertices
$v_{l}(e,P_{t})$ for any edge $e$ that covers $t$ are vertices in the path
$P_{t}^{l}$ and hence we can compare them. We sort the edges $e$ that cover
$t$ according to the vertices $v_{l}(e,P_{t})$ from the closest to the
furthest from $t$. Let $\\{e_{1},...,e_{k}\\}$ be the first $k$ edges in the
sorted order, and let $v_{i}=v_{l}(e_{i},P_{t})$.

First, all edges $t^{\prime}\in P_{t}^{l}$ such that
$\mathsf{Cut}(t,t^{\prime})=k$ are on the subpath of $P_{t}^{l}$ between
$v_{1}$ to $v_{k}$. For this, first note that $v_{1}=u$ as $t=\\{u,p(u)\\}$ is
an edge that covers $t$, and $v_{l}(t,P_{t})=u$, and this is clearly the
closest vertex to $t$ in $P_{t}^{l}$. Second, for any edge $t^{\prime}\in
P_{t}^{l}$ that is below $v_{k}$, there are more than $k$ edges that cross the
cut defined by $\\{t,t^{\prime}\\}$. This follows since the edges
$\\{e_{1},...,e_{k}\\}$ are edges that cover $t$ and not $t^{\prime}$, as the
subpath of $P_{t}^{l}$ they cover is between $u$ to a vertex $v_{i}$ that is
above $t^{\prime}$. Also, the edge $t^{\prime}$ covers $t^{\prime}$ and not
$t$, hence $\mathsf{Cut}(t,t^{\prime})>k$ for these edges.

We divide the edges $t^{\prime}\in P_{t}^{l}$ between $v_{1}$ to $v_{k}$ to
$k-1$ subsets, where $S^{t}_{i}$ is the subpath between $v_{i}$ to $v_{i+1}$
(it can be empty if $v_{i}=v_{i+1}$). Let $c^{t}_{i}=\mathsf{Cov}(t)+k-2i$. We
next show that the tuples $(S^{t}_{i},c^{t}_{i})$ capture all min 2-respecting
cuts $\\{t,t^{\prime}\\}$ where $t^{\prime}\in P_{t}^{l}$. Let $t^{\prime}\in
S^{t}_{i}$, we show that $\mathsf{Cut}(t,t^{\prime})=k$ iff
$\mathsf{Cov}(t^{\prime})=c^{t}_{i}$. By Claim 4.1,
$\mathsf{Cut}(t,t^{\prime})=\mathsf{Cov}(t)+\mathsf{Cov}(t^{\prime})-2\mathsf{Cov}(t,t^{\prime})$.
First, we show that for all edges $t^{\prime}\in S^{t}_{i}$, the value
$\mathsf{Cov}(t,t^{\prime})$ is fixed and equal to $\mathsf{Cov}(t)-i$. Recall
that we sorted the edges that cover $t$ according to the subpath they cover in
$P_{t}^{l}$. Any edge that covers $t$ except $\\{e_{1},...,e_{i}\\}$ covers
the subpath between $u$ to $v_{i+1}$ (and possibly additional edges). As
$t^{\prime}\in S^{t}_{i}$ is in the subpath between $v_{i}$ to $v_{i+1}$ it is
covered by all edges that cover $t$ except $\\{e_{1},...,e_{i}\\}$ that cover
subpaths that end before $S^{t}_{i}$. Hence, we have
$\mathsf{Cov}(t,t^{\prime})=\mathsf{Cov}(t)-i$. This gives
$\mathsf{Cut}(t,t^{\prime})=\mathsf{Cov}(t)+\mathsf{Cov}(t^{\prime})-2\mathsf{Cov}(t,t^{\prime})=\mathsf{Cov}(t)+\mathsf{Cov}(t^{\prime})-2(\mathsf{Cov}(t)-i)$.
This implies that $\mathsf{Cut}(t,t^{\prime})=k$ iff
$\mathsf{Cov}(t^{\prime})=\mathsf{Cov}(t)+k-2i=c^{t}_{i}$, as needed.

By now we dealt with all min 2-respecting cuts where $t^{\prime}\in
P_{t}^{l}$. Similarly, we can define $k-1$ tuples
$(S^{t}_{i+(k-1)},c^{t}_{i+(k-1)})$ that capture min 2-respecting cuts where
$t^{\prime}\in P_{t}^{h}$. Here, we sort the edges $e$ covering $t$ according
to the vertices $v_{h}(e,P_{t})$ from the closest to furthest from $t$, and
again define $c^{t}_{i+(k-1)}=\mathsf{Cov}(t)+k-2i$. Recall that
$v_{h}(e,P_{t})$ is defined such that $e$ covers exactly the subpath of
$P_{t}^{h}$ between $p(u)$ and $v_{h}(e,P_{t})$. Following the same arguments
gives that $\mathsf{Cut}(t,t^{\prime})=k$ for $t^{\prime}\in P_{t}^{h}$ iff
there exists an index $i$ where $t^{\prime}\in S^{t}_{i+(k-1)}$ and
$\mathsf{Cov}(t^{\prime})=c^{t}_{i+(k-1)}$. This completes the proof. ∎

##  7 Learning the Cut Information

We showed that for each tree edge $t$, we can represent in $O(k\log{n})$ bits
information about all min 2-respecting cuts that contain $t$, where $k$ is the
value of the min cut. We next show that all tree edges $t$ can learn this
information efficiently, as well as additional useful information such as the
number of min 2-respecting cuts $\\{t,t^{\prime}\\}$ where $t^{\prime}$ is in
a certain fragment. For the algorithm, we decompose the tree into fragments
using the fragment decomposition from Section 4.2. We also apply on the tree
the LCA labeling scheme from Section 4.3.

We denote by $\mathsf{CutInfo}(t)$ the $O(k\log{n})$ information represented
by the tuples $\\{(S^{t}_{i},c^{t}_{i})\\}_{1\leq i\leq\ell}$ from Lemma 2.3.
Note that $S^{t}_{i}$ is a subpath in the tree represented by two vertices,
$c^{t}_{i}$ is an integer bounded by $m=O(n^{2})$, and $\ell=2(k-1)$, hence
the information indeed can be represented in $O(k\log{n})$ bits. When we learn
about a subpath $S^{t}_{i}$, we will see that we learn the LCA labels of the
endpoints of $S^{t}_{i}$, which in particular include also the fragments of
the endpoints, as explained in Section 4.3. In the proof of Lemma 2.3, we
divided the tuples $\\{(S^{t}_{i},c^{t}_{i})\\}_{1\leq i\leq\ell}$ to two
parts, one is the tuples representing min cuts $\\{t,t^{\prime}\\}$ where the
tree edge $t^{\prime}$ is in the path $P_{t}^{l}$ below $t$, and the second
where the tree edge $t^{\prime}$ is in the path $P_{t}^{h}$, above or
orthogonal to $t$. We denote by $\mathsf{CutInfo}_{l}(t)$, and
$\mathsf{CutInfo}_{h}(t)$ the tuples $\\{(S^{t}_{i},c^{t}_{i})\\}$ divided to
these two parts, such that
$\mathsf{CutInfo}(t)=\mathsf{CutInfo}_{l}(t)\cup\mathsf{CutInfo}_{h}(t)$. We
denote by $\mathsf{FragInfo}(t,F)$ the number of min cuts $\\{t,t^{\prime}\\}$
where $t^{\prime}$ is in the fragment $F$, and by $\mathsf{FragInfo}_{h}(t,F)$
the number of min cuts $\\{t,t^{\prime}\\}$ where $t^{\prime}$ is in the
_highway_ of the fragment $F$. Recall that each fragment is composed of a main
path that is called the _highway_ of the fragment, and additional sub-trees
attached to it called _non-highways_ , see Section 4.2 for the full details.
We next show how tree edges learn the information $\mathsf{CutInfo}(t)$,
$\mathsf{FragInfo}(t,F)$ and $\mathsf{FragInfo}_{h}(t,F)$. We show two
algorithms, one for tree edges $t$ in non-highways, and one for tree edges in
highways. We first discuss a few useful observations.

######  Claim 7.1.

Let $e,e^{\prime}$ be two edges that cover a tree edge $t$, and let $P$ be a
path that contains $t$. We can use LCA computations to compare the vertices
$v_{h}(e,P),v_{h}(e^{\prime},P)$, and check which one is closer to $t$.
Similarly, we can compare $v_{l}(e,P),v_{l}(e^{\prime},P)$ and check which one
is closer to $t$.

###### Proof.

Let $v=v_{h}(e,P),v^{\prime}=v_{h}(e^{\prime},P)$. Both $v$ and $v^{\prime}$
are vertices in $P^{h}$. The path $P^{h}$ starts in the vertex $p(u)$, it has
a part above $p(u)$ that ends in the vertex $a_{P}=LCA(p(u),p_{h})$, and then
a part below $a_{P}$. We can check in which part $v,v^{\prime}$ are using LCA
computations, as the first part is above $p(u)$ and the second is not, so if
$LCA(p(u),v)=v$ we know that $v$ is in the first part, and otherwise it is in
the second part. Now if $v,v^{\prime}$ are in different parts, the closer to
$t$ is the one in the first part. Otherwise, if they are both in the first
part, above $p(u)$, the closer to $t$ is the lower in the path, which can be
checked using LCA computations: $LCA(v,v^{\prime})=v$ iff $v^{\prime}$ is the
lower. Finally, if they are both in the second part, orthogonal to $p(u)$, the
closer to $t$ is the higher, which again can be checked using LCA
computations. To conclude, using the LCA labels alone we can compare the
vertices $v_{h}(e,P)$ and see which one is closer to $t$. Using similar ideas
we can compare $v_{l}(e,P),v_{l}(e^{\prime},P)$ (here we just need to check
which one is higher in the tree). ∎

######  Claim 7.2.

Given $\mathsf{CutInfo}(t)$, the values
$\\{(t^{\prime},\mathsf{Cov}(t^{\prime}))\\}_{t^{\prime}\in F}$ and all LCA
labels of vertices in $F$, as well as indication of which tree edges are part
of the highway of $F$, one can deduce all the min 2-respecting cuts of the
form $\\{t,t^{\prime}\\}$ for $t^{\prime}\in F$. In particular, it can deduce
$\mathsf{FragInfo}(t,F)$ and $\mathsf{FragInfo}_{h}(t,F)$.

###### Proof.

The information $\mathsf{CutInfo}(t)$ is a set of tuples
$(S^{t}_{j},c^{t}_{j})$, for each one of the tuples we would like to check
which edges in $S^{t}_{j}$ with cover value $c^{t}_{j}$ are in the fragment
$F$. Summing the number of such edges for all $j$ gives exactly the number of
min 2-respecting cuts $\\{t,t^{\prime}\\}$ where $t^{\prime}\in F$ from the
definition of $\mathsf{CutInfo}(t)$, this gives $\mathsf{FragInfo}(t,F)$. To
get $\mathsf{FragInfo}_{h}(t,F)$ we sum only cuts where $t^{\prime}$ is on the
highway. We next explain the computation for one such tuple
$(S^{t}_{j},c^{t}_{j})$. The segment $S^{t}_{j}$ is the tree path between
$v_{j}$ to $v_{j+1}$. The information $\mathsf{CutInfo}(t)$ has the LCA labels
and fragments of $v_{j}$ and $v_{j+1}$. We use this information to identify
the intersection of $S^{t}_{j}$ and $F$ (that may be empty), as follows.

  * •

Case 1: $v_{j}$ and $v_{j+1}$ are vertices in $F$. Here the segment
$S^{t}_{j}$ is contained entirely inside $F$. Since we know the complete
structure of the fragment $F$ and the cover values of all edges, we can just
check which edges in the segment $S^{t}_{j}$ have cover value $c^{t}_{j}$ in
this case.

  * •

Case 2: $v_{j}$ and $v_{j+1}$ are vertices outside $F$. Here, we use the
structure of the skeleton tree and the fragments of $v_{j}$ and $v_{j+1}$ to
identify the tree path between them in the skeleton tree, denote this path by
$P_{S}$. Let $r_{F},d_{F}$ be the root and unique descendant of $F$. Recall
that the skeleton tree has one edge $e_{F}=\\{r_{F},d_{F}\\}$ that represents
the highway of $F$. If $P_{S}$ does not contain $e_{F}$, it follows that the
intersection $S^{t}_{j}\cap F$ is empty. Otherwise, $S^{t}_{j}\cap F$ is
exactly the highway of $F$. As we know the cover values of edges in the
highway, we can check which of them have cover value $c^{t}_{j}$, which
completes this case.

  * •

Case 3: exactly one of $v_{j}$ and $v_{j+1}$ is in $F$. Assume w.l.o.g that
$v_{j}\in F$. Here we use the structure of the skeleton tree, and fragment
$F^{\prime}$ of $v_{j+1}$ to identify the closest vertex to $v_{j+1}$ in $F$
(for this, we look at the tree path between $F^{\prime}$ and $F$). This vertex
can only be the root $r_{F}$ or descendant $d_{F}$ of $F$ as they are the only
vertices that connect directly to vertices outside the fragment. Assume
w.l.o.g that $r_{F}$ is the closest vertex to $v_{j+1}$. It follows that the
intersection $S^{t}_{j}\cap F$ is the tree path between $r_{F}$ and $v_{j}$.
As we know the complete structure of $F$ and the cover values of all edges in
the fragment, we can check which edges in this path have cover value
$c^{t}_{j}$, as needed.

∎

###  7.1 The Algorithm for Non-Highways

We next describe the algorithm for learning $\mathsf{CutInfo}(t)$,
$\mathsf{FragInfo}(t,F)$ and $\mathsf{FragInfo}_{h}(t,F)$ for non-highways.
For simplicity, we first present the algorithm for the case that each tree
edge $t$ already knows the tree path $P_{t}$, and we later explain how to
overcome this assumption.

######  Lemma 7.3.

Assume that each non-highway edge $t$ knows the path $P_{t}$. Then all the
non-highway tree edges $t$ can learn $\mathsf{CutInfo}(t)$ in $O(k\sqrt{n})$
time.

###### Proof.

Fix a non-highway tree edge $t=\\{u,p(u)\\}$. We start by computing
$\mathsf{CutInfo}_{h}(t)$. Following the proof of Lemma 2.3, to compute the
tuples $\\{(S^{t}_{i},c^{t}_{i})\\}$ in $\mathsf{CutInfo}_{h}(t)$ we should
sort the edges $e$ covering $t$ according to the vertices $v_{h}(e,P_{t})$,
from the closest to furthest from $t$, and learn about the $k$ first edges
$e_{1},...,e_{k}$ in the sorted order and the corresponding vertices
$v_{1}=v_{h}(e_{1},P_{t}),...,v_{k}=v_{h}(e_{k},P_{t})$. Then, we define
$S^{t}_{i}$ to be the subpath between $v_{i}$ to $v_{i+1}$, and
$c^{t}_{i}=\mathsf{Cov}(t)+k-2i$. The value $\mathsf{Cov}(t)$ is known to $t$
by Claim 4.2, hence to compute $\\{(S^{t}_{i},c^{t}_{i})\\}$ it just needs to
learn about the edges $e_{1},...,e_{k}$ and vertices $v_{1},...,v_{k}$.

To do so, first note that given the LCA labels of the edges $e,t$, and the
endpoints of the path $P_{t}$ we can check if $e$ covers $t$ and if so,
compute the LCA label of the vertex $v_{h}(e,P_{t})$ using Claims 4.12 and
6.3. We can also use the LCA labels to compare two vertices
$v=v_{h}(e,P_{t}),v^{\prime}=v_{h}(e^{\prime},P_{t})$ and see which one is
closer to $t$, using Claim 7.1. Moreover, as $t$ is a non-highway edge, any
edge that covers it has one endpoint in the subtree $T_{u}$ below $t$ (rooted
at $u$) that is in the same fragment of $t$. Hence, for each such edge, there
is one vertex in $T_{u}$ that knows about it. This suggests the following
algorithm. Each vertex in $T_{u}$ first looks at the edges adjacent to it,
checks which ones cover $t$, and compare them according to the vertices
$v_{h}(e,P_{t})$. Then, we start sending suggestions for $t$, a vertex of
height $j$ in the tree, sends to its parent in round $j+i$ the $i$’th best
edge it knows about according to the sorted order, including edges adjacent to
it and edges it received from its children. The $k$ first edges in the sorted
order (and their corresponding vertices $v_{h}(e,P_{t})$) get to $u$ in at
most $O(\sqrt{n}+k)$ rounds. For this, note that a vertex of height $j$,
learns about the $i$’th best edge in its subtree until round $j+i$, as it can
only be delayed by $i-1$ better edges. Hence, in $O(\sqrt{n}+k)$ time $t$
learns $\mathsf{CutInfo}_{h}(t)$. The whole computation is inside the fragment
of $t$.

To let all non-highway edges $t$ learn $\mathsf{CutInfo}_{h}(t)$, we work in
all fragments simultaneously. In each fragment $F$, first all non-highway
edges $t$ send to the whole fragment the LCA labels of $t$ and the endpoints
$\\{p_{l},p_{h}\\}$ of $P_{t}$, this is $O(\sqrt{n})$ pieces of information
hence takes $O(\sqrt{n})$ time. Then, using pipelining, we let each edge $t$
learn about the $k$ best edges that cover it as described above. This takes
$O(\sqrt{n}+k\sqrt{n})=O(k\sqrt{n})$ time overall, as each one of the
$O(\sqrt{n})$ edges should learn $O(k)$ pieces of information.

Computing $\mathsf{CutInfo}_{l}(t)$ can be done exactly in the same manner,
but now comparing edges according to $v_{l}(e,P_{t})$ instead of
$v_{h}(e,P_{t})$. ∎

For a tree edge $t$, we denote by $F_{t}$ the fragment of $t$.

######  Lemma 7.4.

Assume that each non-highway edge $t$ knows the path $P_{t}$. Then all the
non-highway tree edges $t$ can learn $\mathsf{FragInfo}(t,F)$ and
$\mathsf{FragInfo}_{h}(t,F)$ for all fragments $F$ in $O(D+k\sqrt{n})$ time.

###### Proof.

The general proof idea is as follows. For each non-highway tree edge $t$, we
define $O(k)$ special fragments where the segments $S^{t}_{i}$ start or end.
With these special fragments $F$ we would like to talk directly via an edge
between $F_{t}$ and $F$ (if exists) and use it to compute
$\mathsf{FragInfo}(t,F)$ and $\mathsf{FragInfo}_{h}(t,F)$. For non-special
fragments or special fragments where there is no direct edge between $F_{t}$
and $F$, we show that it is enough to broadcast $O(\sqrt{n})$ information to
the whole graph to compute the values $\mathsf{FragInfo}(t,F)$ and
$\mathsf{FragInfo}_{h}(t,F)$. We next describe the algorithm in detail.

##### Step 1: Broadcasting information.

We broadcast the following information. First, in each fragment $F$, we let
all vertices in $F$ learn $\\{t,\mathsf{Cov}(t),\mathsf{CutInfo}(t)\\}$ for
all tree edges $t\in F$, we also learn which ones of the tree edges are
highways. As this is at most $O(k\log{n})$ bits of information per edge, we
can broadcast the whole information inside each fragment in $O(k\sqrt{n})$
time. Second, we let all the vertices in the graph learn the following
information about each fragment. Let $c_{F}$ be the minimum cover value of an
edge in the highway $h_{F}$ of $F$, and let $n_{F}$ be the number of edges $t$
in $h_{F}$ such that $\mathsf{Cov}(t)=c_{F}$. The values $(c_{F},n_{F})$ can
be computed locally in $F$ in $O(\sqrt{n})$ time by scanning the highway. We
let all vertices in the graph learn $(c_{F},n_{F})$ for all fragments $F$. As
there are $O(\sqrt{n})$ fragments, broadcasting this information over a BFS
tree takes $O(D+\sqrt{n})$ time from Claim 4.13.

##### Step 2: Special fragments.

For a non-highway tree edge $t$, we define $O(k)$ special fragments as
follows. First, $F_{t}$ is a special fragment, as well as the first and last
fragments in the path $P_{t}$. Second, recall that each segment $S^{t}_{i}$ is
a segment between two vertices $v_{i}$ and $v_{i+1}$. Let $F_{i}$ be the
fragment of $v_{i}$. If $v_{i}$ is an internal vertex in the fragment (i.e.,
not the root or the descendant of the fragment), the fragment $F_{i}$ is
special. Overall we have $O(k)$ special fragments, as we have $O(k)$ segments
$S^{t}_{i}$. Note that $t$ knows the fragments $F_{i}$ as it knows the LCA
labels of the vertices $v_{i}$, and the fragment $F_{i}$ is part of the label
of $v_{i}$ (see Section 4.3).

For each special fragment $F$, we would like to use an edge between $F_{t}$ to
$F$ to compute the values $\mathsf{FragInfo}(t,F)$ and
$\mathsf{FragInfo}_{h}(t,F)$. We first focus on special fragments $F$ where
there is indeed an edge between $F_{t}$ and $F$, and later discuss the case
there is no edge. For technical reasons, we focus on the existence of
_internal edges_ between the fragments, where we say that an edge between two
fragments is _internal_ if it connects two internal vertices in the fragments.
A useful property of internal edges is that such edges that connect different
pairs of fragments are disjoint, as any internal vertex only belongs to one
fragment. Note that we can check in $O(\sqrt{n})$ time if there is an internal
edge from the fragment $F_{t}$ to each one of the $O(\sqrt{n})$ fragments in
the graph, and if so find such an edge, by aggregate computations in the
fragment. Let $e=\\{v,w\\}$ be an internal edge connecting $v\in F_{t}$ and
$w\in F$. Since $v\in F_{t}$ it knows $\mathsf{CutInfo}(t)$ as we broadcast
this information to the whole fragment. Also, as $w\in F$ it knows the
complete structure of $F$ and all the cover values of edges in the fragment,
as we broadcast this information to the whole fragment. By Claim 7.2, using
this information $v$ and $w$ can deduce $\mathsf{FragInfo}(t,F)$ and
$\mathsf{FragInfo}_{h}(t,F)$. This only requires $v$ to send to $w$ the value
$\mathsf{CutInfo}(t)$, and then $w$ can compute $\mathsf{FragInfo}(t,F)$ and
$\mathsf{FragInfo}_{h}(t,F)$ and send it to $v$ that can later send it to $t$.

For each special fragment $F$, we use an internal edge to $F_{t}$ if exists to
compute $\mathsf{FragInfo}(t,F)$ and $\mathsf{FragInfo}_{h}(t,F)$. Then we
send the information computed to $t$ by broadcast in the fragment. Note that
each tree edge $t$ should learn at most $O(k)$ values, hence overall we can
broadcast the whole information to all $O(\sqrt{n})$ tree edges $t$ in the
fragment in $O(k\sqrt{n})$ time. We can work in parallel in different
fragments, as internal edges connecting different fragments are disjoint,
resulting in $O(k\sqrt{n})$ complexity for this part.

##### Step 3: Special fragments with no internal edge.

Here we show that if there are no internal edges between $F_{t}$ and $F$, then
it is easy to compute $\mathsf{FragInfo}(t,F)$ and
$\mathsf{FragInfo}_{h}(t,F)$. This is the only step in the proof where we use
the fact that $t$ is a non-highway edge. First, if $t^{\prime}\in F$ such that
$\mathsf{Cut}(t,t^{\prime})=k$, then $t^{\prime}$ is a highway edge. To see
this, assume to the contrary that $t^{\prime}$ is a non-highway edge, note
that non-highway edges in different fragments are orthogonal to each other
from the structure of the fragment decomposition. If $\\{t,t^{\prime}\\}$ is a
min 2-respecting cut, then from Claim 4.6 there is an edge between the subtree
below $t$ and the subtree below $t^{\prime}$. However, these trees are
composed of internal vertices of the fragment (as $t$ and $t^{\prime}$ are
non-highways) implying there is an internal edge between $F_{t}$ and $F$, a
contradiction.

Also, for any non-tree edge $e$ that covers $t$, $e$ either covers all the
highway of $F$ or covers none of the edges in $F$. This holds as one of the
endpoints of $e$ is an internal vertex in $F_{t}\neq F$ (as it is in the
subtree below $t$) and the other is not an internal vertex in $F$, as there
are no internal edges between the fragments. Hence, both the endpoints of $e$
are not internal vertices in $F$. Then, from Claim 4.9, $e$ either covers
exactly the highway of $F$ or does not cover any edge of $F$. This implies
that the value $\mathsf{Cov}(t,t^{\prime})$ for $t^{\prime}$ in the highway of
$F$ does not depend on the specific choice of $t^{\prime}$, denote this value
by by $\mathsf{Cov}(t,F)$. This value can be computed by $t$ as follows. This
is the cost of all edges that cover $t$ and $h_{F}$. We can run an aggregate
computation in $F_{t}$ to sum the costs of these edges: at the end each vertex
$u\in F_{t}$ learns the cost of edges that have an endpoint below $u$ in
$F_{t}$ and cover $h_{F}$. For the vertex $u$ such that $t=\\{u,p(u)\\}$ this
is exactly $\mathsf{Cov}(t,F)$. Hence all non-highway edges $t\in F$ learn
$\mathsf{Cov}(t,F)$. Moreover, we can compute these values for all fragments
$F$ where there are no internal edges between $F_{t}$ to $F$, as there are
$O(\sqrt{n})$ fragments, the whole computation takes $O(\sqrt{n})$ time using
pipelining. Now $\mathsf{Cut}(t,t^{\prime})=k$ for $t^{\prime}\in h_{F}$ iff
$\mathsf{Cov}(t)+\mathsf{Cov}(t^{\prime})-2\mathsf{Cov}(t,t^{\prime})=k$. As
$\mathsf{Cov}(t,t^{\prime})=\mathsf{Cov}(t,F)$, this holds iff
$\mathsf{Cov}(t^{\prime})=k-\mathsf{Cov}(t)+2\mathsf{Cov}(t,F)$. Moreover, if
$\\{t,t^{\prime}\\}$ is min 2-respecting cut, then
$\mathsf{Cov}(t^{\prime})=c_{F}$ must be the minimum cover value of an edge in
$h_{F}$, as otherwise, for an edge with
$\mathsf{Cov}(t^{\prime\prime})=c_{F}$, we get that
$\mathsf{Cut}(t,t^{\prime\prime})=\mathsf{Cov}(t)+c_{F}-2\mathsf{Cov}(t,F)<\mathsf{Cov}(t)+\mathsf{Cov}(t^{\prime})-2\mathsf{Cov}(t,F)=k$,
contradiction to the fact $k$ is the minimum cut value. To conclude, to
compute $\mathsf{FragInfo}(t,F)$ that is equal to $\mathsf{FragInfo}_{h}(t,F)$
in this case, $t$ should learn how many edges in $h_{F}$ have
$\mathsf{Cov}(t^{\prime})=k-\mathsf{Cov}(t)+2\mathsf{Cov}(t,F)=c_{F}$. If
$k-\mathsf{Cov}(t)+2\mathsf{Cov}(t,F)\neq c_{F}$, there are no such edges.
Otherwise, the number of such edges is exactly $n_{F}$, the number of edges in
$h_{F}$ with $\mathsf{Cov}(t^{\prime})=c_{F}$. As all vertices know $c_{F}$
and $n_{F}$ for all fragments, then $t$ can compute this locally using
$\mathsf{Cov}(t)$ and $\mathsf{Cov}(t,F)$.

##### Step 4: Non-special fragments.

We first show that if $F$ is a non-special fragment for $t$, then the only
edges $t^{\prime}\in F$ that may be part of a min 2-respecting cut
$\\{t,t^{\prime}\\}$ are highway edges. Additionally, we show that the highway
of $F$ is either completely contained in one of the segments $S^{t}_{i}$ or
its intersection with all segments $S^{t}_{i}$ is empty (in which case
$\mathsf{FragInfo}(t,F)$=0). For this, first look at the tree path $P_{t}$,
this path contains all the edges $t^{\prime}$ such that
$\mathsf{Cut}(t,t^{\prime})=k$ by definition. From the structure of the
skeleton tree, any tree path in the graph between two fragments $F_{1}$ and
$F_{2}$ can only contain complete highways of other fragments. Hence, except
of the first and last fragments of $P_{t}$ that are special, the intersection
of $P_{t}$ with any other fragment $F$ is either $h_{F}$ or empty. Moreover,
from the structure of the skeleton tree and from the first and last fragments
of $P_{t}$, $t$ can deduce all the fragments that intersect the path $P_{t}$.
Let $F$ be a non-special fragment such that $F\cap P=h_{F}$. As $F$ is non-
special, we know that all vertices $v_{i}$ are not internal vertices of $F$.
If we look at the path $P_{t}$, as it contains $h_{F}$, we can find an index
$i$ such that $v_{i}$ is in $P_{t}$ before $h_{F}$, and $v_{i+1}$ is in
$P_{t}$ after $h_{F}$. Or in other words, there is a unique segment
$S^{t}_{i}$ such that $h_{F}\subseteq S^{t}_{i}$. Moreover, $t$ can compute
this segment as it knows the fragments of all vertices $v_{i}$. Now, from
Lemma 2.3, we have that for $t^{\prime}\in S^{t}_{i}$,
$\mathsf{Cut}(t,t^{\prime})=k$ iff $\mathsf{Cov}(t^{\prime})=c^{t}_{i}$.
Moreover, for any edge in $S^{t}_{i}$, we have $\mathsf{Cov}(t^{\prime})\geq
c^{t}_{i}$. For this, first note that $\mathsf{Cov}(t,t^{\prime})$ is fixed
for all edges in $S^{t}_{i}$ as explained in the proof of Lemma 2.3. Hence if
we have an edge $t^{\prime\prime}\in S^{t}_{i}$ where
$\mathsf{Cov}(t^{\prime\prime})<c^{t}_{i}$, we get that
$\mathsf{Cut}(t,t^{\prime\prime})=\mathsf{Cov}(t)+\mathsf{Cov}(t^{\prime\prime})-2\mathsf{Cov}(t,t^{\prime\prime})<\mathsf{Cov}(t)+c^{t}_{i}-2\mathsf{Cov}(t,t^{\prime})=\mathsf{Cut}(t,t^{\prime})=k$,
where $t^{\prime}$ is an edge in $S^{t}_{i}$ with
$\mathsf{Cut}(t,t^{\prime})=k$, contradicting the fact that $k$ is the min cut
value. To conclude, we need to check how many edges $t^{\prime}\in h_{F}$ have
$\mathsf{Cov}(t^{\prime})=c^{t}_{i}$. If the minimum cover value $c_{F}$ of an
edge in $h_{F}$ is greater than $c^{t}_{i}$, there are no such edges.
Otherwise $c_{F}=c^{t}_{i}$ (it cannot be smaller from the discussion above),
and we have that $\mathsf{FragInfo}(t,F)=n_{F}$. As $t$ knows the values
$c_{F},n_{F}$ for all fragments and the values $c^{t}_{i}$, it can deduce
$\mathsf{FragInfo}(t,F)$ for all non-special fragments. As explained, all
edges $t^{\prime}$ in a min 2-respecting cut with $t$ in this case are highway
edges, hence $\mathsf{FragInfo}_{h}(t,F)=\mathsf{FragInfo}(t,F)$ in this case.
∎

##### Dealing with the case that $P_{t}$ is not initially known.

During the proof we assumed for simplicity that the path $P_{t}$ is known to
the edge $t$. We now explain how to extend the algorithm to the case it is not
known. In [DEMN21], the authors show how each tree edge learns a set of
$\mathop{\mathrm{missing}}{poly}(\log{n})$ paths that includes the path
$P_{t}$ (the path $P_{t}$ is called the _interesting path_ for $t$, where the
paths found are called the _potentially interesting_ paths). The time
complexity of the algorithm in [DEMN21] is $\tilde{O}(D+\sqrt{n})$. We can
extend our algorithm to work with this information, with a poly-logarithmic
overhead in the complexity. Here, we just repeat the algorithm poly-
logarithmic number of times with all the possible choices for the path
$P_{t}$. Note that if we run the algorithm for $t$ with a path $P\neq P_{t}$,
it follows from the proof that if we learn about a tuple
$(S^{t}_{i},c^{t}_{i})$, all the edges $t^{\prime}\in S^{t}_{i}$ where
$\mathsf{Cov}(t^{\prime})=c^{t}_{i}$ are such that
$\mathsf{Cut}(t,t^{\prime})=k$. The only difference is that if we work with a
path $P\neq P_{t}$ we are not guaranteed that the tuples computed contain all
the tree edges $t^{\prime}$ where $\mathsf{Cut}(t,t^{\prime})=k$, where for
the right choice for $P_{t}$ we are guaranteed to find all cuts. Since in the
algorithm we compute $\mathsf{FragInfo}(t,F)$ for all fragments $F$, each tree
edge $t$ can compute the number of min 2-respecting cuts $\\{t,t^{\prime}\\}$
found for any choice of path $P$. Then it chooses $P_{t}$ as the path where
this number is maximal. This path $P_{t}$ necessarily contains all edges
$t^{\prime}$ where $\mathsf{Cut}(t,t^{\prime})=k$, because we know that all
the cuts found are indeed min cuts, and we know that one of the paths $t$
tries is the right path $P_{t}$. Trying poly-logarithmic number of options
adds poly-logarithmic overhead to the complexity. Note that from the
discussion above, after trying all options the tree $t$ learns about the path
$P_{t}$, giving the following.

######  Lemma 7.5.

All the non-highway tree edges $t$ can learn $\mathsf{CutInfo}(t)$,
$\mathsf{FragInfo}(t,F)$ and $\mathsf{FragInfo}_{h}(t,F)$ for all $F$, and the
identity of the path $P_{t}$ in $\tilde{O}(D+k\sqrt{n})$ time.

###  7.2 The Algorithm for Highways

We next explain how highway edges learn the cut information. As explained
above, in [DEMN21] it is shown that each edge $t$ learns a set of
$O(\log^{2}{n})$ paths that contains the path $P_{t}$.

######  Lemma 7.6 ([DEMN21]).

In $\tilde{O}(D+\sqrt{n})$ time, each tree edge $t$ learns about a set of
paths of size $O(\log^{2}{n})$ that contains the path $P_{t}$.

For the highway case, we need a stronger guarantee that also follows from
[DEMN21].

######  Lemma 7.7 ([DEMN21]).

Let $F$ be a fragment with highway $h_{F}$. The edges of each highway can
learn a set of paths $Q_{h}$ of size $O(\log^{2}{n})$ that contains all the
paths $\\{P_{t}^{h}|t\in h_{F},v_{h}\not\in F\\}$ and a set of paths $Q_{l}$
of size $O(\log^{2}{n})$ that contains all the paths $\\{P_{t}^{l}|t\in
h_{F},v_{l}\not\in F\\}$. The time complexity is $\tilde{O}(D+\sqrt{n})$.

This lemma follows as a corollary of Lemma 5.13 in [DEMN21] as is also
explained in [DEMN21]. Lemma 7.7 would allow us to deal efficiently with paths
$P_{t}$ that have endpoints outside $F_{t}$, dealing with paths that are
contained in $F_{t}$ will be similar to the non-highway case.

In our algorithm, initially tree edges do not know $P_{t}$, but just a poly-
logarithmic number of options for the path $P_{t}$, that include the correct
path $P_{t}$. We denote by $\mathsf{CutInfo}(t,P)$ the value
$\mathsf{CutInfo}(t)$ when $t$ assumes that the path $P_{t}=P$. For the
correct option $\mathsf{CutInfo}(t,P_{t})=\mathsf{CutInfo}(t)$. Similarly we
define $\mathsf{FragInfo}(t,F,P)$ to be $\mathsf{FragInfo}(t,F)$ where $t$
assumes that $P_{t}=P$. During our algorithm each tree edge computes the
values $\mathsf{CutInfo}(t,P)$, $\mathsf{FragInfo}(t,F,P)$ and
$\mathsf{FragInfo}_{h}(t,F,P)$ for $O(\log^{2}{n})$ options for the path $P$
that contain the correct choice $P_{t}$. All the values computed indeed
describe min cuts containing $t$, but if $P\neq P_{t}$, we may not find all
cuts. Eventually, $t$ can identify the correct path $P_{t}$ as it chooses the
path where $\sum_{F}\mathsf{FragInfo}(t,F,P)$ is maximal.

For the tree edge $t$ we denote by $Q_{t}$ the set of $O(\log^{2}{n})$
potential candidates for $P_{t}$ that $t$ learns about in Lemmas 7.6 and 7.7.

######  Lemma 7.8.

In $\tilde{O}(D+k\sqrt{n})$ time, each highway tree edge $t$ can learn
$\mathsf{CutInfo}(t,P)$ for each $P\in Q_{t}$.

###### Proof.

Fix a highway tree edge $t=\\{u,p(u)\\}$ in a fragment $F_{t}$. We focus on
learning $\mathsf{CutInfo}_{h}(t,P)$, learning $\mathsf{CutInfo}_{l}(t,P)$ can
be done in a similar manner. We divide into cases depending if the endpoint
$v_{h}$ of $P$ is inside $F_{t}$ or not.

##### Case 1: $v_{h}\in F_{t}$.

Here for each tree edge $t$ we fix one path $P\in Q_{t}$ with $v_{h}\in F_{t}$
(if exists). Repeating the algorithm $O(\log^{2}{n})$ times would cover all
paths $P$ in this case, and would add $O(\log^{2}{n})$ term to the complexity.
As explained before, our goal is to learn about $k$ edges
$e_{1},e_{2},...,e_{k}$ and corresponding endpoints $v_{1},...,v_{k}$ that
define the segments $S^{t}_{i}$. These edges may have an internal endpoint
inside $F_{t}$ or not. We first learn about $k$ relevant edges
$e^{\prime}_{1},...,e^{\prime}_{k}$ that have at least one internal endpoint
in $F_{t}$. Here our goal is to learn about $k$ edges that cover $t$ and their
endpoints $v_{h}(e,P)$ are the closest to $t$. This can be done exactly as in
the proof of the non-highway case (Lemma 7.3), and takes $O(k\sqrt{n})$ time
for all tree edges $t$. We next consider edges that both their endpoints are
not internal vertices in $F_{t}$, we call them _global_ edges. Here we use
Claim 4.9 that states that every edge that both its endpoints are not internal
vertices in $F_{t}$ either covers the complete highway of $F_{t}$ or does not
cover any edge of $F_{t}$. This means that for any global edge that covers
$t$, the part of $P^{h}$ it covers is exactly $P^{h}\cap h_{F}$, where $h_{F}$
is the highway of $F_{t}$, this path is exactly the segment from $p(u)$ to
$LCA(p(u),v_{h})$ (this contains exactly all highway edges above
$t=\\{u,p(u)\\}$ in $P_{t}^{h}$). Let $v^{\prime}=LCA(p(u),v_{h})$. To
determine the segments $S^{t}_{i}$, we want $t$ to learn how many global edges
cover $t$, denote this number by $global_{t}$. This information together with
the edges $e^{\prime}_{1},...,e^{\prime}_{k}$ computed before allows to
determine the vertices $v_{1},...,v_{k}$ that define the segments $S^{t}_{i}$.
To do so, we sort the vertices
$v_{h}(e^{\prime}_{1},P),...,v_{h}(e^{\prime}_{k},P),v^{\prime}$ according to
their closeness to $t$, where the vertex $v^{\prime}$ appears $global_{t}$
times (once per each relevant edge that covers the segment between $t$ and
$v^{\prime}$). Finally we take the $k$ closest endpoints according to this
order, and they define the segments $S^{t}_{i}$. Note that the only
information we needed to learn about global edges is the number of edges that
cover the whole highway $h_{F}$, this information is not specific for $t$. To
learn this information we can use global communication over a BFS tree to sum
the number of such edges. Doing this for all fragments $F$ takes
$O(D+\sqrt{n})$ time. Hence, overall the computation in this case takes
$\tilde{O}(D+k\sqrt{n})$ time.

##### Case 2: $v_{h}\not\in F_{t}$.

We next consider the case that $v_{h}$ is outside $F_{t}$. We first explain
how to handle one highway edge $t$ and fix one path $P\in Q_{t}$ from this
case, and then show how to do the computation efficiently for all highway
edges. To determine the segments $S^{t}_{i}$, exactly as the previous case we
start by learning the $k$ closest edges to $t$ that cover $P^{h}$ and have at
least one internal endpoint in $F_{t}$, denote them by
$e^{\prime}_{1},...,e^{\prime}_{k}$. We next turn our attention to edges that
cover $P^{h}$ and both their endpoints are not internal vertices in $F_{t}$.
Each such edge covers the whole highway $h_{F}$. For each such edge we can
compute $v_{h}(e,P^{h})$. We can use a global communication over a BFS tree to
learn the $k$ global edges where the vertices $v_{h}(e,P^{h})$ are the closest
to $F_{t}$. This takes $O(D+k)$ time for one path $P^{h}$. At the end of the
computation, the tree edge $t$ can determine the segments $S^{t}_{i}$ by
sorting the endpoints $\\{v_{h}(e^{\prime}_{i},P)\\}_{1\leq i\leq k}$ it
learned about locally, and the endpoints $v_{h}(e,P)$ of the $k$ global edges
closest to $F_{t}$ it learns in the global communication. Taking the $k$
closest vertices defines the segments $S^{t}_{i}$ as needed.

We next explain how to do the computation efficiently for all highway edges.
As in previous cases, finding the local edges can be done for all edges in
$O(k\sqrt{n})$ time, the main challenge is finding the global edges. If for
each edge $t$, there is a different path $P^{h}$ to consider, this part can
take linear time, which is too expensive. Here we exploit Lemma 7.7 that
implies that there is a set $Q_{h}$ of $O(\log^{2}{n})$ size that contains all
the paths $\\{P_{t}^{h}|t\in h_{F},v_{h}\not\in F\\}$. Hence, we just need to
consider $O(\log^{2}{n})$ paths for all different highway edges in $h_{F}$.
Hence, and since there are $O(\sqrt{n})$ fragments, we can compute $S^{t}_{i}$
for all highway edges in $\tilde{O}(D+k\sqrt{n})$ time via pipelining. ∎

######  Lemma 7.9.

All the highway tree edges $t$ can learn $\mathsf{FragInfo}(t,F,P)$ and
$\mathsf{FragInfo}_{h}(t,F,P)$ for all fragments $F$ and $P\in Q_{t}$ in
$\tilde{O}(D+k\sqrt{n})$ time.

###### Proof.

For the proof, we again first fix one path $P\in Q_{t}$ for each edge $t$. The
proof generally follows the proof of Lemma 7.4, most of the steps in the proof
apply for highway tree edges as well. In particular, dealing with special
fragments where there is a direct internal edge to them, or dealing with non-
special fragments can be done exactly the same. The only difference is in Step
3 which we describe now. In Step 3, the tree edge $t$ learns
$\mathsf{FragInfo}(t,F,P)$ for special fragments $F$ where there is no
internal edge between $F_{t}$ and $F$. We focus on learning about min
2-respecting cuts $\\{t,t^{\prime}\\}$ where $t^{\prime}\in P^{h}$. Dealing
with the case that $t^{\prime}\in P^{l}$ can be done in the same manner. Note
that we only need to consider edges $t$ where $P^{h}$ ends outside $F_{t}$, as
otherwise the claim trivially holds. We first show that there is only a
limited number of options for the identity of the fragment $F$. If $F\neq
F_{t}$ is a special fragment for $t$ where $F\cap P^{h}\neq\emptyset$ it can
be either the last fragment $F_{last}$ of $P^{h}$, or there is at least one
internal vertex $v_{i}\in F$ that is an endpoint of one of the segments
$S^{t}_{i}$. We first deal with the latter case.

##### Case 1: $F\neq F_{last}$.

Here, by the definition of the segments $S^{t}_{i}$, there is an edge $e$ that
covers $t=\\{u,p(u)\\}$ where $v_{h}(e,P^{h})=v_{i}\in F$. We show that if
$F\neq F_{last}$, then $e$ must be a global edge found in the global
communication phase described in the proof of Lemma 7.8. Assume to the
contrary that $e=\\{v_{l},v_{h}\\}$ is an edge that has an internal endpoint
in $F_{t}$. Note that the second endpoint of $e$ cannot be an internal vertex
in $F$, as there are no internal edges between $F_{t}$ and $F$. Let $p_{h}$ be
the endpoint of $P^{h}$ in $F_{last}$, and $v_{h}$ be the endpoint of $e$ that
is above or orthogonal to $t$. From the discussion above $v_{h}$ is not an
internal vertex in $F$. Recall that by the definition of
$v_{i}=v_{h}(e,P^{h})$ it can be equal either to
$a_{e}=LCA(p(u),v_{h}),a_{P}=LCA(p(u),p_{h})$ or $LCA(p_{h},v_{h})$, where
$p(u)\in F_{t}\neq F,p_{h}\in F_{last}\neq F$ and $v_{h}$ is not an internal
vertex in $F$, in all cases we get that $v_{h}(e,P^{h})$ cannot be an internal
vertex in $F$, as the LCA of two vertices that are not internal vertices in
$F$ cannot be an internal vertex in $F$ by Claim 4.10, a contradiction.

To conclude, we have that if $v_{h}(e,P^{h})\not\in F_{last}$ then it is an
endpoint of one of the $k$ global edges covering $t$ that were found in the
global communication phase. Note that the identity of $F_{last}$ and of the
$k$ global edges depends only on $P^{h}$, and not on the specific choice of
$t$. Hence, for any $P^{h}$ there are only at most $O(k)$ options for the
fragment $F$. We call these fragments the special fragments of $P^{h}$. For
any special fragment of $P^{h}$, we would like to learn globally the following
information. Let $e^{g}_{1},...,e^{g}_{k}$ be the global edges found in the
global communication phase, and let $u_{i}=v_{h}(e^{g}_{i},P^{h})$. We first
broadcast the information $(P^{h},F_{t},u_{1},...,u_{k})$ to the whole graph,
which allows the whole graph learn the identity of the special fragments of
$P^{h}$. For a special fragment $F\neq F_{last}$ of $P^{h}$ where there are no
internal edges between $F$ and $F_{t}$, let $u_{i_{1}},...,u_{i_{t}}$ be the
vertices of $u_{1},...,u_{k}$ inside $F$ (there is at least one by the
definition of special fragment), ordered by closeness to $t$. Let $a_{F}$ and
$b_{F}$ be the closest and furthest vertices from $t$ on the highway of $F$
(one is the root and one is the unique descendant of the fragment). We look at
the subpaths $a_{F}-u_{i_{1}},u_{i_{1}}-u_{i_{2}},...,u_{i_{t}}-b_{F}$ and for
each one of those subpaths $S$, we find the minimum cover value of the
subpath, $c_{S}$, and the number of times it appears in the subpath $S$. Each
vertex in $F$ can learn this information locally as it knows the cover values
of all edges in $F$. We then broadcast the information $(S,c_{S},n_{S})$ for
all relevant subpaths to the whole graph. Note that for any path $P^{h}$ we
overall broadcast $O(k)$ messages of $O(\log{n})$ bits, and since there are
$O(\log^{2}{n})$ paths $P^{h}$ relevant for each fragment from Lemma 7.7, the
whole communication takes $\tilde{O}(D+k\sqrt{n})$ time.

We now show that this information suffices for a tree edge $t$ to learn
$\mathsf{FragInfo}(t,F,P)$ and $\mathsf{FragInfo}_{h}(t,F,P)$, for a special
fragment $F\neq F_{last}$ (with respect to $P$) with no internal edges between
$F_{t}$ and $F$. First note that the paths $P^{h}$ that could be relevant for
$t$ are among the $O(\log^{2}{n})$ paths $P^{h}$ relevant for the fragment
(described in Lemma 7.7), hence $t$ learned information about them as
described above. We next fix one such path $P^{h}$. As explained above, $F$
must be one of the special fragments of $P^{h}$. Let $S^{t}_{i}$ be a segment
that intersects $F$. As explained above all the edges $e$ that cover $t$ where
$v_{h}(e,P^{h})\in F$ must be global edges. It follows that the segment
$S^{t}_{i}\cap F$ is one of the subpaths $S$ of $F$ computed before, and that
$t$ knows the values $(S,c_{S},n_{S})$. Now edges $t^{\prime}\in S$ define a
cut of size $k$ with $t$ iff $\mathsf{Cov}(t^{\prime})=c^{t}_{i}$. Also, for
all edges in $S^{t}_{i}$ the value $\mathsf{Cov}(t,t^{\prime})$ is fixed,
which implies that $\mathsf{Cov}(t^{\prime})\geq c^{t}_{i}$ (as $k$ is the min
cut value). It means that there are edges in $S$ where
$\mathsf{Cov}(t^{\prime})=c^{t}_{i}$ iff $c^{t}_{i}=c_{S}$, in which case the
number of these edges is $n_{S}$. Hence $t$ can determine the number of min
2-respecting cuts in any segment $S^{t}_{i}\cap F$. Note that it can also
check for any segment $S$ if it is contained in $S^{t}_{i}$ using the LCA
labels of the endpoints of a segment. Note that all the cuts we learn about
are cuts where $t^{\prime}$ in on a highway in this case, hence
$\mathsf{FragInfo}_{h}(t,F,P)=\mathsf{FragInfo}(t,F,P)$. This completes the
case that $F\neq F_{last}.$

##### Case 2: $F=F_{last}$.

We are left with the case that $F=F_{last}$ and there are no internal edges
between $F$ and $F_{t}$ (as otherwise this case is already covered in Step 2).
We would like to follow a similar algorithm with slight changes. Note that the
edges $e_{1},e_{2},...,e_{k}$ that define the segments $S^{t}_{i}$ are either