  Algorithms for dynamically maintaining minimum spanning trees (MSTs) have
received much attention in both the parallel and sequential settings. While
previous work has given optimal algorithms for dense graphs, all existing
parallel batch-dynamic algorithms perform polynomial work per update in the
worst case for sparse graphs. In this paper, we present the first
work-efficient parallel batch-dynamic algorithm for incremental MST, which can
insert $\ell$ edges in $O(\ell \log(1+n/\ell))$ work in expectation and
$O(\text{polylog}(n))$ span w.h.p. The key ingredient of our algorithm is an
algorithm for constructing a compressed path tree of an edge-weighted tree,
which is a smaller tree that contains all pairwise heaviest edges between a
given set of marked vertices. Using our batch-incremental MST algorithm, we
demonstrate a range of applications that become efficiently solvable in
parallel in the sliding-window model, such as graph connectivity, approximate
MSTs, testing bipartiteness, $k$-certificates, cycle-freeness, and maintaining
sparsifiers.
