  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=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.
