# A Fast Algorithm for Source-wise Round-trip Spanners

Chun Jiang Zhu<EMAIL_ADDRESS>Song Han<EMAIL_ADDRESS>Kam-Yiu
Lam<EMAIL_ADDRESS>Dept. of Computer Science, Univ. of North Carolina
at Greensboro, Greensboro, NC, USA  Dept. of Computer Science and Engineering,
University of Connecticut, Storrs, CT, USA  Dept. of Computer Science, City
University of Hong Kong, Hong Kong, China

###### Abstract

In this paper, we study the problem of fast constructions of source-wise
round-trip spanners in weighted directed graphs. For a source vertex set
$S\subseteq V$ in a graph $G(V,E)$, an $S$-sourcewise round-trip spanner of
$G$ of stretch $k$ is a subgraph $H$ of $G$ such that for every pair of
vertices $u,v\in S\times V$, their round-trip distance in $H$ is at most $k$
times of their round-trip distance in $G$. We show that for a graph $G(V,E)$
with $n$ vertices and $m$ edges, an $s$-sized source vertex set $S\subseteq V$
and an integer $k>1$, there exists an algorithm that in time
$O(ms^{1/k}\log^{5}n)$ constructs an $S$-sourcewise round-trip spanner of
stretch $O(k\log n)$ and $O(ns^{1/k}\log^{2}n)$ edges with high probability.
Compared to the fast algorithms for constructing all-pairs round-trip spanners
[26, 12], our algorithm improve the running time and the number of edges in
the spanner when $k$ is super-constant. Compared with the existing algorithm
for constructing source-wise round-trip spanners [36], our algorithm
significantly improves their construction time
$\Omega(\min\\{ms,n^{\omega}\\})$ (where $\omega\in[2,2.373)$ and 2.373 is the
matrix multiplication exponent) to nearly linear $O(ms^{1/k}\log^{5}n)$, at
the expense of paying an extra $O(\log n)$ in the stretch. As an important
building block of the algorithm, we develop a graph partitioning algorithm to
partition $G$ into clusters of bounded radius and prove that for every $u,v\in
S\times V$ at small round-trip distance, the probability of separating them in
different clusters is small. The algorithm takes the size of $S$ as input and
does not need the knowledge of $S$. With the algorithm and a reachability
vertex size estimation algorithm, we show that the recursive algorithm for
constructing standard round-trip spanners [26] can be adapted to the source-
wise setting. We rigorously prove the correctness and computational complexity
of the adapted algorithms. Finally, we show how to remove the dependence on
the edge weight in the source-wise case.

###### keywords:

Graph spanners , Round-trip spanners , Graph algorithms , Graph partitioning

##  1 Introduction

Graph spanners are sparse graph structures approximating shortest path
distances in graphs and have received considerable research interests since
they were proposed in the late 80’s [28]. A spanner of _stretch_ $\alpha$
($\alpha$-spanner) for an undirected graph $G(V,E)$ is a subgraph
$H(V,E^{\prime}\subseteq E)$ of $G$ such that for every pair of vertices
$u,v\in V$, their distance in $H$ is at most $\alpha$ times their original
distance in $G$. It is well-known that for an integer $k>1$, every graph on
$n$ vertices has a $(2k-1)$-spanner of size (number of edges) $O(n^{1+1/k})$
[6, 32]. The stretch-size trade-off is optimal if we believe the Erdos’s girth
Conjecture [21]. Research efforts were then devoted to $\beta$-additive
spanners and $(\alpha,\beta)$-spanners. In the formers, the distance between
every vertex pair is no larger than their distance in the original graph by
only an additive term $\beta$. Existing studies show that for an undirected
graph, there exists a $2$-additive spanner of size $O(n^{3/2}\log n)$ [4]
(with the log factor shaved in [19]), a $4$-additive spanner of size
$\widetilde{O}(n^{7/5})$ [11], and a 6-additive spanner of size $O(n^{4/3})$
[7, 35], where the notation $\widetilde{O}(\cdot)$ hides polylogarithmic
factors. Abboud _et al._ [1] proved that one cannot obtain an additive spanner
with a constant surplus $\beta=O(1)$ using size $O(n^{4/3-\epsilon})$. In the
latter, the distance between every vertex pair is no larger than $\alpha\cdot
d+\beta$ where $d$ is their distance in the original graph. For the different
constructions of $(\alpha,\beta)$-spanners and other variants of spanners,
readers are referred to [19, 33, 29, 7, 5, 2, 3, 9].

The definition of spanners can be naturally extended to directed graphs
(digraphs) but it becomes trivial to study spanners in this setting because of
the well-known lower bound $\Omega(n^{2})$ on the size [31]. Instead of
studying one-way distances in digraphs, Cowen and Wagner [15, 16] studied
round-trip distances for the first time. The _round-trip distance_ between
vertex $u$ and $v$ in a digraph $G$ is the sum of the one-way distance from
$u$ to $v$ and the one-way distance from $v$ to $u$ in $G$. A _$k$ -roundtrip
spanner_ of $G$ is a subgraph $H$ of $G$ such that for every $u,v$ in $G$,
their round-trip distance in $H$ is at most $k$ times of their original round-
trip distance in $G$. In [15, 16], Cowen and Wagner studied the round-trip
routing schemes which implied a $(2^{k}-1)$-roundtrip spanner of size
$\widetilde{O}(n^{1+1/k})$. Later, Roditty _et al._ [31] significantly
improved the spanner stretch by proposing a randomized algorithm that
constructs a $(2k+\epsilon)$-roundtrip spanner of size
$O(\min\\{(k^{2}/\epsilon)n^{1+1/k}\log(nw),(k/\epsilon)^{2}n^{1+1/k}\log^{2-1/k}n\\})$
essentially in time $\Omega(\min\\{mn,n^{\omega}\\})$ with
$\omega\in[2,2.373)$ (2.373 is the matrix multiplication exponent), for a
graph with $n$ vertices, $m$ edges, maximum edge weight $w$, and a parameter
$\epsilon>0$. Zhu and Lam [37] developed a deterministic algorithm that
constructs a $(2k+\epsilon)$-roundtrip spanner of size
$O((k/\epsilon)n^{1+1/k}\log(nw))$ in the same running time, reducing the size
of the spanner of Roditty _et al._ [31] by a factor of $k$. Recently, Cen _et
al._ [10] further reduced the stretch to $2k-1$. Their deterministic algorithm
constructs a $(2k-1)$-roundtrip spanner of size $O(kn^{1+1/k}\log n)$ in
$\widetilde{O}(kmn\log w)$ time.

However, the runtimes of the algorithms [31, 37, 10] are
$\Omega(\min\\{mn,n^{\omega}\\})$, which is essentially the same as that of
computing All-Pairs Shortest Paths (APSP) [25, 34]. Pachocki _et al._ [26]
proposed a nearly linear time $O(mn^{1/k}\log^{5}n)$ algorithm that constructs
an $O(k\log n)$-roundtrip spanner of size $O(n^{1+1/k}\log^{2}n)$ with high
probability. Their algorithm combines exponential distribution based graph
decomposition [24] and sampling based reachability vertex size estimation
[13]. The former enables reasoning about the probability of separating two
vertices of bounded round-trip distance in different clusters. In the graph
decomposition, they choose a subset of vertices as the centering vertices to
construct clusters such that their algorithm terminates in only logarithmic
levels of recursions. They also proposed an algorithm that constructs a nearly
tight additive round-trip spanner of additive term $O(n^{\alpha})$ and size
$\widetilde{O}(n^{2-\alpha})$ in time $\widetilde{O}(mn^{1-\alpha})$ with high
probability, for an unweighted graph and a parameter $\alpha\in(0,1)$.
Recently, Chechik et al. [12] improved the multiplicative spanner stretch to
$O(k\log\log n)$ and $O(k\log k)$ respectively, while using the same run-time
as the algorithm in [26]. In addition, they developed an
$\tilde{O}(m\sqrt{n})$ time algorithm that computes an
$(8+\epsilon)$-roundtrip spanner of expected $O(n^{1.5})$ edges. Later in
[18], the stretch factor was improved to $(5+\epsilon)$ for the same running
time.

Source-wise Spanners. Another research thread focuses on constructing graph
structures that approximate distances only for _some pairs_ of vertices,
instead of all pairs. Coppersmith and Elkin [14] for the first time studied
exact pair-wise preservers. Given an undirected graph $G(V,E)$ and a set of
pairs of vertices, $P\subseteq V\times V$, a subset of $G$, $H$, is called a
$P$-pairwise preserver of $G$ if for every vertex pair in $P$, their distance
in $H$ is the same as that in $G$. They proved that for a set of vertex pairs
$P$ of size $p$, every graph $G$ contains a $P$-pairwise preserver of size
$O(\min\\{np^{1/2},n+n^{1/2}p\\})$. Recently, Bodwin [8] obtained a size bound
of the pair-wise preserver, $O(n+n^{2/3}p)$, even in the case of digraphs.
Roditty _et al._ [30] worked on source-wise spanners. For a set of _sources_
$S\subseteq V$, a subset of $G$, $H$, is called an $S$-sourcewise $k$-spanner
of $G$ if for every vertex pair in $S\times V$, their distance in $H$ is at
most $k$ times of the distance in $G$. They proposed an algorithm that
constructs an $S$-sourcewise $(2k-1)$-spanner of size $O(kns^{1/k})$ in
expected $\widetilde{O}(kms^{1/k})$ time, where $s$ is the size of $S$.
Further work along this direction studied source-wise spanners with an
_additive_ stretch. There have also been polynomial-time algorithms
constructing $S$-sourcewise spanners of additive stretches $2$,$4$, and $6$,
and sizes $\widetilde{O}(n^{5/4}s^{1/4})$ [23],
$\widetilde{O}(n^{11/9}s^{2/9})$, and $O(n^{6/5}s^{1/5})$ [22], respectively.
See other stretch-size trade-offs of source-wise spanners and source-wise
spanners for the setting $S\times S$ in [17, 27, 29].

Recently, source-wise round-trip spanners, a natural extension of standard
round-trip spanners in the source-wise setting, were firstly studied by Zhu
and Lam [36]. Given a set of sources $S$ in a digraph $G$, a subgraph $H$ of
$G$ is called an _$S$ -sourcewise $k$-roundtrip spanner_ of $G$ if for every
$u\in S,v\in V$, their round-trip distance in $H$ is at most $k$ times of
their round-trip distance in $G$. Source-wise round-trip spanners can have
applications for computing the source-wise variants of round-trip compact
routing schemes, distance oracles and low distortion embeddings [36]. They
proposed an algorithm that in time $\Omega(\min\\{ms,n^{\omega}\\})$
constructs an $S$-sourcewise $(2k+\epsilon)$-roundtrip spanner of size
$O((k^{2}/\epsilon)ns^{1/k}\log(nw))$. However, the construction time of the
algorithm, $\Omega(\min\\{ms,n^{\omega}\\})$, is quite large, especially when
the size $s$ is a large integer. It is natural to ask whether the fast
algorithm for constructing standard round-trip spanners [26] can be adapted to
the source-wise setting.

Contributions. In this paper, we provide an affirmative answer to the above
question and show a generalization of the algorithms of [26] for the all-pairs
construction to the source-wise setting, trading off computation time for
stretch. As an important building block, we first develop a graph partitioning
algorithm to partition a graph $G$ into clusters of bounded radius, and prove
that for vertex $u$ in a source vertex set $S$ and $v\in V$ at small round-
trip distance, the probability of separating them in different clusters is
small. The algorithm does not require the knowledge of $S$ but only its size
$|S|$. The second algorithm is an algorithm for estimating the sizes of in-
balls and out-balls around some center vertices with a radius. Informally, an
in-ball (out-ball) around a vertex $u$ with a radius $r$ is the vertices that
$u$ can be reachable ($u$ can reach, respectively) within distance $r$. It can
perform size estimations for some subset of vertices $U$, instead of all
vertices $V$. For a small $U$, the algorithm is more efficient compared to
Cohen’s algorithm [13]. With the two algorithms at hand, we show that the
recursive algorithm for constructing standard round-trip spanners [26] can be
adapted to the source-wise setting by thoroughly setting the source vertex set
in every recursion. Furthermore, we rigorously prove the correctness and
computational complexity of the adapted algorithms. Finally, we show how to
remove the dependence of the edge weights in the source-wise setting. Our main
result is summarized in the following theorem.

######  Theorem 1 (Improved Source-wise Round-trip Spanners).

For a weighted directed graph $G(V,E)$ on $n$ vertices and $m$ edges, a source
vertex set $S\subseteq V$ of size $s$ and an integer $k>1$, there is an
algorithm that in time $O(ms^{1/k}\log^{5}n)$ constructs an $S$-sourcewise
$O(k\log n)$-roundtrip spanner of size $O(ns^{1/k}\log^{2}n)$ with high
probability.

Compared with the existing algorithm [36] for constructing source-wise round-
trip spanners, our result significantly improves their construction time
$\Omega(\min\\{ms,n^{\omega}\\})$ (where $\omega\in[2,2.373)$) to a nearly
linear time $O(ms^{1/k}\log^{5}n)$. The expense is that the stretch of the
spanner is worsened by a factor of $\log n$. Note that the round-trip spanners
preserving alll-pairs round-trip distances are feasible source-wise round-trip
spanners. Compared to the fast algorithm for constructing all-pairs round-trip
spanners [26], we reduce the size of the spanner from $O(n\cdot
n^{1/k}\log^{2}n)$ to $O(n\cdot s^{1/k}\log^{2}n)$, and improve the
construction time from $O(m\cdot n^{1/k}\log^{5}n)$ to $O(m\cdot
s^{1/k}\log^{5}n)$ when $k$ is super-constant.

######  Remark 1.

The maximum value of $k$ to consider in the setting of multiplicative spanners
is bounded by $O(\log n)$. When $k=O(\log n)$, the performance of the spanner
constructed in Theorem 1 is the same as that in the algorithm of [26]. When
$k$ is a constant, the spanner in Theorem 1 has stretch $O(\log n)$ and size
$\widetilde{O}(n^{1+c})$ for some constant $c$. The size is larger than the
nearly linear $\widetilde{O}(n)$ size of the spanner of the same stretch by
the algorithm of [10] while the nearly linear run-time is much faster than the
$\Omega(mn)$ time in [10]. However, when $k$ is super-constant, our algorithm
can still bring subpolynomial benefits in both the run-time and the size of
the spanner compared to the algorithms of [26, 12].

The remainder of this paper is organized as follows. In Section 2, we present
the notations and definitions we will use. Next, we provide technical details
of our algorithms for constructing source-wise round-trip covers in Section 3,
and then describe the removal of the dependence of edge weights in Section 4.
Finally, we conclude the paper with a brief discussion on the future work in
Section 5.

##  2 Notations and Definitions

We consider weighted directed graphs $G(V,E,W)$, where $V$ and $E$ are the
vertex set and edge set and $W$ assigns weight $W(e)$ to an edge $e\in E$.
Throughout the paper let $n=|V|$ and $m=|E|$ denote the number of vertices and
the number of edges in $G$, and $w=\max_{e\in E}W(e)$ denote the maximum edge
weight. Let $G(U)$ denote the subgraph induced by an arbitrary set of vertices
$U$. We use $d_{G}(u,v)$ to denote the _(one-way shortest) distance_ from $u$
to $v$ in $G$. The _round-trip distance_ between $u$ and $v$ in $G$, denoted
by $d_{G}(u\rightleftarrows v)=d_{G}(u,v)+d_{G}(v,u)$, is the distance from
$u$ to $v$ plus the distance from $v$ to $u$. We drop the subscript $G$ if it
is clear from context. The _radius_ and _diameter_ of $G$ are defined as
$\min_{u\in V}\max_{v\in V}d(u,v)$ and $\max_{u,v\in V}d(u,v)$, respectively.
Similarly, the _round-trip radius_ of $G$ is $\min_{u\in V}\max_{v\in
V}d(u\rightleftarrows v)$. We allow that there may be multiple round-trip
shortest paths between two vertices.

A _(round-trip) ball_ with round-trip radius $R$ around vertex $u$ in $G(U)$,
denoted as $ball_{U}(u,R)$, is the set of vertices with round-trip distance no
larger than $R$ from $u$ in $G(U)$. Similarly, let $out$-$ball_{U}(u,r)$ and
$in$-$ball_{U}(u,r)$ denote the set of vertices that can be reached from $u$
or can reach $u$ within distance $r$ in $G(U)$, respectively. A shortest path
out-tree from vertex $v$ to a subset of vertices $U$ in $G$ is a subgraph $T$
of $G$ s.t. $T$ is a tree rooted at $v$ with all edges oriented away from $v$,
and for every $u\in U$, $d_{G}(v,u)=d_{T}(v,u)$. Similarly a shortest path in-
tree from $U$ to $v$ is a subgraph $T$ of $G$ s.t. $T$ is a tree rooted at $v$
with all edges oriented towards from $v$, and for every $u\in U$,
$d_{G}(u,v)=d_{T}(u,v)$. We define the _round-trip tree_ of a ball
$B=ball_{U}(v,R)$, denoted by $RT$-$Tree(B)$, as the union of a shortest path
out-tree from $v$ to all vertices of $B$ and a shortest path in-tree from all
vertices of $B$ to $v$ in $G(U)$. We say that an event happens _with high
probability (w.h.p.)_ if it happens with probability $O(1-1/n^{c})$, where $n$
is the size of the input of the problem and $c$ is a constant.

##  3 An Algorithm for Constructing Source-wise Round-trip Spanners

Following existing methods for constructing round-trip spanners [31, 36, 26],
the key subroutine is the construction of _round-trip covers_ : a collection
of round-trip balls of a bounded radius such that each pair of vertices at a
small round-trip distance is contained in at least one of the balls. In
addition, every vertex is required to be included in a bounded number of
balls. The notion of source-wise round-trip covers is formally defined below,
while our result for their efficient construction are summarized in Theorem 2.

######  Definition 1 (Source-wise Round-trip Covers [36]).

For a graph $G(V,E)$ and a vertex set $S\subseteq V$, a collection $C$ of
round-trip balls is called an $S$-sourcewise $(k,R)$-cover if and only if (1)
each ball in $C$ has round-trip radius at most $k\cdot R$; and (2) for every
$u\in S,v\in V$ of round-trip distance at most $R$, they are contained in the
same ball $B\in C$.

######  Theorem 2 (Improved Source-wise Round-trip Covers).

For a graph $G(V,E)$, a source vertex set $S\subseteq V$ of size $s$, an
integer $k>1$ and a parameter $R>0$, there is an algorithm that in time
$O(ms^{1/k}\log^{4}n)$ constructs an $S$-sourcewise $(O(k\log n),R)$-cover $C$
w.h.p. Furthermore, each vertex $v\in V$ is contained in $O(s^{1/k}\log n)$
balls.

Compared to the previous construction of source-wise round-trip covers [36],
the running time is improved to a nearly linear time. But the stretch-size
trade-off is worse as there is a $\log n$ factor in the stretch. With the
algorithm for constructing source-wise round-trip covers, we immediately get
an algorithm for constructing source-wise round-trip spanners through a
standard technique [31]. Specifically, for each logarithmic scale of round-
trip distances $[2^{i-1},2^{i})$ where $1\leq i\leq\log_{2}(2nw)$, we
construct source-wise $(O(k\log n),2^{i})$-cover $C_{i}$ w.r.t. $S$. We then
take the union of $RT$-$Tree(B)$ for each $B\in\cup_{1\leq
i\leq\log_{2}(2nw)}C_{i}$ as the resulting $S$-sourcewise $O(k\log
n)$-roundtrip spanner. Therefore, the number of edges in the source-wise
round-trip spanner and the running time contain a term of $\log(nw)$ as in
Theorem 3. In the remainder of this section, we first present the fast
algorithm for constructing source-wise round-trip covers. Then in the next
section, we prove our main theorem (Theorem 1) by removing the dependence on
the maximum edge weight $w$.

######  Theorem 3 (An intermediate result for source-wise round-trip
spanners).

For a graph $G(V,E)$, a source vertex set $S\subseteq V$ of size $s$ and an
integer $k>1$, there is an algorithm that in time
$O(ms^{1/k}\log^{4}n\cdot\log(nw))$ constructs an $S$-sourcewise $O(k\log
n)$-roundtrip spanner of size $O(ns^{1/k}\log n\cdot\log(nw))$ w.h.p.

High-Level Ideas. Our algorithm is an extension of the fast algorithm for
constructing standard round-trip covers [26] to the source-wise setting. We
follow their recursive idea that is based on the following case analysis. If
there is a vertex $u$ with a large in- and out-ball of radius $r>0$, then we
include the round-trip ball $ball(u,O(r))$ into the cover and recurse on the
graph induced by the remaining vertices $G(V-ball(u,O(r)))$. Otherwise, we
partition the graph using a source-wise graph partitioning algorithm and then
recurse on each part of the partitioning. See the illustrating examples for
the two cases in Figure 1. For both cases, we show that we need to recurse at
most a logarithmic number of times because the graph size is reduced by at
least a constant factor in each recursion. We are able to prove that every
pair $u,v\in S\times V$ at small round-trip distance has a small probability
to appear in different balls. Finally, repeating this procedure multiple times
and taking union of the obtained balls result in the source-wise round-trip
cover.

In order to develop the above algorithm, we need to generalize its component
algorithms from the standard setting to the source-wise setting. Specifically,
a source-wise graph partitioning algorithm is used to compute a partitioning
of vertices in $G$ with the following properties: (i) all parts, except for
one, have a bounded round-trip radius, (ii) the last part has bounded size,
and (iii) every pair $u,v\in S\times V$ has a small probability to appear in
different parts. This algorithm does not require the knowledge of $S$ and only
its cardinality $|S|$ suffices to guarantee the desirable properties. A
sampling-based algorithm is used to estimate the sizes of in- and out-balls.
The recursive algorithm for constructing source-wise round-trip covers is an
adaptation of the standard algorithm by adapting the exploration radius and
carefully setting the source vertex set in every recursion.

(a) The first case

(b) The second case

Figure 1: Recursions under the two cases, where source vertices are labeled in
red color. (a) There is a vertex $a$ that can reach $\\{a,b,c,f\\}$ and be
reachable from $\\{a,b,c,d\\}$ within within distance 1. The sizes of both
reachability sets are no smaller than a pre-defined threshold 4. Then we
include the ball $ball(a,2\cdot 1)=\\{a,b,c\\}$ into the cover and recurse on
the graph induced by the remaining vertices $\\{d,e,f\\}$. (b) There is no
vertex that can reach and be reachable from at least 4 vertices within
distance 1. Then we apply a graph partitioning algorithm to get two clusters
(separated by the dash line), $\\{a,b,c\\}$ and $\\{d,e,f\\}$, and recurse on
the graph induced by each cluster.

In the sequel, we first present the two subroutines in Sections 3.1 and 3.2,
respectively, and then discuss the algorithm for constructing source-wise
round-trip covers in Section 3.3.

###  3.1 A Source-wise Graph Partitioning Algorithm

In order to apply the recursive idea, we need a graph partitioning/clustering
algorithm that partitions the vertices of an input graph into clusters of
small round-trip radius. More importantly, we need to reason that the
probability that the cycle of interest cut by the partitioning (with vertices
in different parts) is small. We show that this can be achieved by growing
balls with radius deliberately chosen from an exponential distribution with
the appropriate parameter. Graph partitioning using the exponential
distribution is not new and appeared in several prior works [24, 20, 26].
Miller _et al._ [24] proposed a parallel low-diameter decomposition algorithm
on undirected graphs that can reason that not too many edges are cut by the
decomposition. Ene _et al._ [20] studied partitioning for directed graphs
instead of undirected graphs. They show that the probability that the
partitioning cuts edges cannot be bounded but one can reason the probability
that cycles are cut is small. Later, Pachocki _et al._ [26] enhanced the
algorithms of [24, 20] by providing the capability of growing clusters rooted
at a specific set of vertices. We take a step further by generalizing the
partitioning algorithm in [26] to the multiple-source setting. For any sources
$S\subseteq V$. we can reason that every pair $u,v$ in $S\times V$ at small
round-trip distance has a small probability to appear in different parts.
Moreover, we observe that the knowledge of the set $S$ is not required in this
algorithm.

The partitioning algorithms Cluster-Out and Cluster-In are presented in
Algorithm 1. The input set of vertices $U$ is the chosen set of centers to
build clusters while $s$ is the size of a source vertex set $S$. Cluster-Out
independently assigns each vertex $u\in U$ a random radius $r_{u}$ drawn from
the exponential distribution with the parameter $\log(s)/r$. The exponential
distribution Exp$(\beta)$ with parameter $\beta$ has probability density
function $f(x)=\beta exp(-\beta x)$ on $x\geq 0$. Note that the parameter we
use is $\log(s)/r$ and this is essentially the only crucial change to
generalize the algorithm of [26] to the source-wise setting. Each vertex $v\in
V$ is assigned to the cluster centered at vertex $u\in U$ which maximizes
$r_{u}-d(u,v)$ if the quantity is larger than 0. Otherwise, $v$ is assigned to
the last cluster. The algorithm can be implemented as parallel ball growing
similar to [24, 20]. We first pick a start time $r_{u}$ for every vertex $u\in
U$ from Exp$(\log(s)/r)$, and then explore the graph by starting a search from
$u$ at time $r_{u}$ if $u$ is not already reached by some other vertex. The
search takes $W(e)$ time to propagate across an edge $e$, and each time step
can be performed in parallel over all vertices in $U$. Each vertex $v$ in $V$
is assigned to the cluster rooted at the vertex $u$ that reaches it first.

The properties of Algorithm 1 are summarized in Theorem 4. To prove the
theorem, we need to show the properties of the exponential distribution
Exp$(\beta)$. By the cumulative distribution function of the exponential
distribution, we have for any $x\geq 0$, the probability that $T\geq x$,
denoted as $Pr[T\geq x]$, is $exp(-\beta x)$.

$Pr[T\geq x]=exp(-\beta x).$

The _memoryless_ property of the exponential distribution is that for any
$s,t\geq 0$,

$Pr[T\geq s+t\,|\,T\geq s]=Pr[T\geq t].$

Algorithm 1 Cluster-Out(Cluster-In)$(G(V,E),U,r,s)$

0: $G(V,E)$, a vertex set $U\subseteq V$, an integer $s\geq 2$ and a parameter
$r>0$

0: $(V_{1},\cdots,V_{d})$

1: $\beta\leftarrow\log(s)/r$;

2: For each $u\in U$, picks a radius $r_{u}$ from Exp$(\beta)$ independently;

3: For each $v\in V$, assigns $v$ to the cluster centered at vertex $u\in U$
which maximizes $r_{u}-d(u,v)$ if the quantity is positive; otherwise, do not
assign $v$ to any cluster; (assigns $v$ to the cluster centered at vertex
$u\in U$ which maximizes $r_{u}-d(v,u)$, respectively);

4: $(V_{1},\cdots,V_{d-1})\leftarrow$ the clusters constructed in Line 3;

5: $V_{d}\leftarrow V-\cup_{i\in[1,d-1]}V_{i}$;

6: return ($V_{1},\cdots,V_{d-1},V_{d}$);

######  Theorem 4.

For a graph $G(V,E)$, an arbitrary set of vertices $U\subseteq V$, a fixed but
unknown set of vertices $S$ of size $s\geq 2$, and a parameter $r>0$,
Algorithm 1 constructs a partitioning $(V_{1},\cdots,V_{d})$ of $V$ such that,
(1) all clusters $V_{1},\cdots,V_{d-1}$, except for the last cluster $V_{d}$,
have a radius at most $c\cdot r$ with probability at least $1-n/s^{c}$ for
$c\geq 1$;
(2) the last cluster $V_{d}$ has size at most $|V|-|U|$;
(3) for every $u,v\in S\times V$ s.t. $d(u\rightleftarrows v)\leq R$, they are
in the same cluster $V_{i}$ with probability at least $exp(-R/r\cdot\log s)$.
Furthermore, the algorithm runs in time $O(m\log n)$.

###### Proof.

For brevity, we only prove the theorem for the routine Cluster-Out. The proof
for Cluster-In is similar and omitted here. We first prove property (1). By
construction, each cluster $V_{i}$ for $i\in[1,d-1]$ can have radius at most
$r_{u}$, where $u$ is the center of $V_{i}$. Then according to the cumulative
distribution function of the exponential distribution, we have that

$Pr[r_{u}\geq c\cdot r]=exp(-c\cdot\beta r)\leq s^{-c}.$

By union bound, the event that all clusters $V_{1},\cdots,V_{d-1}$ have radius
at most $c\cdot r$ happens with probability at least $1-n/s^{c}$.

Next we prove property (2). We show that each $u\in U$ will be assigned to the
cluster centered at $u$ itself, if there exists no vertex $u^{\prime}\in U$
such that $r_{u^{\prime}}-d(u^{\prime},u)>r_{u}$. This is because
$r_{u}-d(u,u)=r_{u}>0$ and it meets the requirements of adding a vertex to a
cluster. Otherwise, $u$ will be assigned to another cluster $u^{\prime}\not=u$
which maximizes $r_{u^{\prime}}-d(u^{\prime},u)$. In either case $u$ is
included in some cluster $V_{i}$ for $i\in[1,d-1]$. That is,

$|\cup_{i\in[1,d-1]}V_{i}|\geq|U|.$

Then by construction we have

$\begin{split}|V_{d}|=&|V-\cup_{i\in[1,d-1]}V_{i}|\\\
\leq&|V|-|\cup_{i\in[1,d-1]}V_{i}|\\\ \leq&|V|-|U|.\end{split}$

For property (3), we indeed prove a stronger argument: for every $u,v\in
V\times V$, instead of $u,v\in S\times V$, at round-trip distance at most $R$,
they are in the same cluster $V_{i}$ with probability at least $exp((-R/r)\log
s)$. Assume that $x\in U$ is the vertex which maximizes
$r_{x}-\min\\{d(x,u),d(x,v)\\}$ and that the quantity is larger than $0$
(otherwise, both $u$ and $v$ are contained in $V_{d}$.) Let $T$ be the second
largest value of this quantity or zero, whichever is larger. Suppose without
loss of generality (w.l.o.g.) that $d(x,u)\leq d(x,v)$. Then $u$ is assigned
to the cluster $V_{i}$ centered at $x$ and $r_{x}-d(x,u)\geq T$. $u$ and $v$
are separated in different balls only if $r_{x}-d(x,v)<T$. This would imply
that

$\begin{split}&r_{x}-(d(x,u)+R)\\\ \leq&r_{x}-d(x,u)-d(u\rightleftarrows v)\\\
<&r_{x}-d(x,u)-d(u,v)\\\ \leq&r_{x}-d(x,v)<T\end{split}$

The second to last inequality holds because of the triangle inequality. By the
memoryless property of the exponential distribution, the probability of both
vertices $u$ and $v$ containing in the same cluster $V_{i}$ is at least

$Pr[r_{x}\geq d(x,u)+R+T\,|\,r_{x}\geq d(x,u)+T]=exp(-\beta
R)=exp(-R/r\cdot\log s).$

We now analyze the running time. The algorithm can be implemented sequentially
as follows. First, we add a virtual root $r$ and connect it to each of $u\in
U$ with an edge of weight $0$. Then we perform a shortest path search from $r$
to all vertices in $V$. The partitioning of $V$ can be inferred easily from
the shortest path tree. So the running time is dominated by that of a single-
source shortest path search using Fibonacci heaps, $O(m+n\log n)=O(m\log n)$.
∎

###  3.2 Estimating the Sizes of In- and Out-Balls

Here we present a random sampling based algorithm for estimating the sizes of
in- and out-balls around some selected vertices. It is an adaptation of
Cohen’s algorithm [13] (see also a similar algorithm in [26]) to the multiple
source setting. The algorithm takes in a subset of vertices $U$ in a graph $G$
and parameters $r>0$, $\epsilon\in(0,1)$, and estimates the sizes $f_{In}^{u}$
and $f_{Out}^{u}$ of the $in$-$ball_{V}(u,r)$ and $out$-$ball_{V}(u,r)$ for
every vertex $u$ in $U$ such that the estimations are no larger or smaller
than $f_{In}^{u}$ and $f_{Out}^{u}$ by at most $\epsilon$, respectively. As in
Algorithm 2, we first sample a subset $T$ of vertices from $V$ and compute
distances between vertices in $T$ and $U$, e.g., by constructing a single-
source shortest path tree for each vertex in either $T$ or $U$, whichever has
a smaller cardinality. Based on the distances, we can then calculate the
estimations of $f_{In}^{u}$ and $f_{Out}^{u}$ with the desirable accuracy. The
properties of Cohen’s algorithm is summarzied in Lemma 1 while the properties
of Algorithm 2 is summarized in Corollary 1. In our subsequent algorithms, we
will call Algorithm 2 with $U=V$. However, the algorithm enjoys the
flexibility that can perform size estimations for some subset of vertices $U$,
instead of all vertices $V$.

Algorithm 2 Estimate-In-Out-
Balls($G(V,E),r,\epsilon,U=\\{u_{1},\cdots,u_{d}\\}$)

0: G(V,E), a vertex set $U$, parameters $r>0$ and $\epsilon\in(0,1)$

0: $\widetilde{F}_{Out},\widetilde{F}_{In}$

1: Sample $t=\lceil 5\epsilon^{-2}\log n\rceil$ vertices
$T=\\{v_{1},\cdots,v_{t}\\}$ uniformly at random independently from $V$ with
replacement;

2: Compute the distances between each of $U=\\{u_{1},\cdots,u_{d}\\}$ and each
of $T=\\{v_{1},\cdots,v_{t}\\}$, e.g., by building a singe-source shortest
path tree from each vertex in either $T$ or $U$, whichever has a smaller
cardinality;

3:
$\widetilde{F}_{Out}\leftarrow\\{[\widetilde{f}_{Out}^{u_{1}},\cdots,\widetilde{f}_{Out}^{u_{d}}]\,|\,\widetilde{f}_{Out}^{u_{i}}\leftarrow$
the fraction of vertices $v\in T$ such that $d(u_{i},v)\leq r$ for
$i\in[1,d]\\}$;

4:
$\widetilde{F}_{In}\leftarrow\\{[\widetilde{f}_{In}^{u_{1}},\cdots,\widetilde{f}_{In}^{u_{d}}]\,|\,\widetilde{f}_{In}^{u_{i}}\leftarrow$
the fraction of vertices $v\in T$ such that $d(v,u_{i})\leq r$ for
$i\in[1,d]\\}$;

5: return ($\widetilde{F}_{Out},\widetilde{F}_{In}$);

######  Lemma 1 ([13]).

For a graph $G(V,E)$, an arbitrary vertex set $U$ of size $d$, parameters
$r>0$ and $\epsilon\in(0,1)$, let $F_{Out}$ ($F_{In}$) be the $n$-length
vector such that the value corresponding to a vertex $u\in V$, $f_{Out}^{u}$
($f_{In}^{u}$), is the fraction of vertices $v\in V$ such that $d(u,v)\leq r$
($d(v,u)\leq r$, resp.). There is an algorithm that constructs their
estimations $\widetilde{F}_{Out}$ and $\widetilde{F}_{In}$ such that for every
$u\in V$, both the inequalities
$\widetilde{f}_{Out}^{u}-f_{Out}^{u}\leq\epsilon$ and
$\widetilde{f}_{In}^{u}-f_{In}^{u}\leq\epsilon$ hold w.h.p. Furthermore, the
algorithm runs in time $O(m\epsilon^{-2}\log^{2}n)$.

######  Corollary 1.

For a graph $G(V,E)$, an arbitrary vertex set $U$ of size $d$, parameters
$r>0$ and $\epsilon\in(0,1)$, let $F_{Out}$ ($F_{In}$) be the $d$-length
vector such that the value corresponding to a vertex $u\in U$, $f_{Out}^{u}$
($f_{In}^{u}$), is the fraction of vertices $v\in V$ such that $d(u,v)\leq r$
($d(v,u)\leq r$, resp.). Algorithm 2 constructs their estimations
$\widetilde{F}_{Out}$ and $\widetilde{F}_{In}$ such that for every $u\in U$,
both the inequalities $\widetilde{f}_{Out}^{u}-f_{Out}^{u}\leq\epsilon$ and
$\widetilde{f}_{In}^{u}-f_{In}^{u}\leq\epsilon$ hold w.h.p. Furthermore, the
algorithm runs in time $O(\min\\{\epsilon^{-2}\log n,d\\}m\log n)$.

###### Proof.

Under the Chernoff bound, we easily have that

$Pr[\widetilde{f}_{Out}^{u}-f_{Out}^{u}>\epsilon]\leq 2\cdot
exp(-2t\epsilon^{2})\leq 2\cdot exp(-10\log n)=2n^{-10}<0.002.$

By a similar application of the Chernoff bound, the inequality for
$\widetilde{f}_{In}^{u}$ also holds. The run-time is dominated by
$O(\min\\{t,d\\})$ invocations of single-source shortest path search using
Fibonacci heaps in Line 2. ∎

###  3.3 Source-wise Round-trip Cover Construction

With Algorithms 1 and 2 at hand, we are ready to describe the algorithm for
constructing source-wise round-trip covers. As mentioned earlier, this
algorithm is an adaptation of the algorithm of [26] for constructing standard
round-trip covers. Much of the adatation work is performed in a subroutine
RecursiveCover for the simpler task of constructing a recursive cover that is
a partitioning of the vertex set such that for every vertex pair of interest
at bounded round-trip distance, they are in the same part with at least some
fixed probability $p$. The main source-wise round-trip cover construction is
then a union of sufficiently many recursive covers computed by RecursiveCover
to raise the fixed probability $p$ to a high probability bound. Through
careful adaptation of the exploration radius and the source vertex set in
every recursion, we achieve a probability $p$ dependent on $\log s$ instead of
$\log n$ required in the standard setting. That means only
$\widetilde{O}(s^{1/k})$ recursive covers instead of $\widetilde{O}(n^{1/k})$
are sufficient to secure the high probability bound, leading to a smaller size
of source-wise round-trip covers.

Algorithm 3 RecursiveCover$(G(V,E),r,S)$

0: $G(V,E)$, a source vertex set $S$, and a parameter $r>0$

0: $C$

1: Let $c\geq 1$ be a sufficiently large constant;

2: if $V=\emptyset$ $||$ $S=\emptyset$ then

3: return $\emptyset$; {Handle the special cases when $V=\emptyset$ or
$S=\emptyset$}

4: end if

5: if $|S|=1$ then

6: Let $u$ be the only vertex in $S$; {Handle the special case when $|S|=1$}

7: $B\leftarrow ball_{V}(u,r)$;

8: return $C\leftarrow\\{B\\}$;

9: end if

10: $(\widetilde{F}_{Out},\widetilde{F}_{In})\leftarrow$ Estimate-In-Out-
Balls$(G,c\cdot r,1/8,V)$;

11: Let $U_{Out}\leftarrow\\{u\in V\,|\,\widetilde{f}_{Out}^{u}\geq 3/4\\}$
and $U_{In}\leftarrow\\{u\in V\,|\,\widetilde{f}_{In}^{u}\geq 3/4\\}$;

12: if $U_{Out}\cap U_{In}\not=\emptyset$ then

13: if $|U_{Out}\cap U_{In}|<1/4\cdot|V|$ then

14: return $\\{V\\}$; {Failure exit 1}

15: end if

16: Choose a vertex $u\in U_{Out}\cap U_{In}$ arbitrarily, and let the round-
trip radius $r_{u}$ assigned to $u$ be a uniformly random value in $[2c\cdot
r,2(c+1)\cdot r]$;

17: $B\leftarrow ball_{V}(u,r_{u})$;

18: return $C\leftarrow\\{B\\}$ $\cup$ RecursiveCover$(G(V-B),r,S-B)$;

19: else

20: if $|U_{Out}|\leq 1/2\cdot|V|$ then

21: $(V_{1},\cdots,V_{d})\leftarrow$ Cluster-Out$(G,V-U_{Out},r,|S|)$;

22: else

23: $(V_{1},\cdots,V_{d})\leftarrow$ Cluster-In$(G,V-U_{In},r,|S|)$;

24: end if

25: if $\max_{1\leq i\leq d}|V_{i}|>7/8\cdot|V|$ then

26: return $\\{V\\}$; {Failure exit 2}

27: end if

28: for $1\leq i\leq d$ do

29: $S_{i}\leftarrow S\cap V_{i}$; {Update each source vertex set}

30: end for

31: return $C\leftarrow\text{RecursiveCover}(G(V_{1}),r,S_{1})\text{
}\cup\cdots\cup\text{ }\text{RecursiveCover}(\newline G(V_{d}),r,S_{d})$;

32: end if

The algorithm presented in Algorithm 3 takes in a source vertex set $S$ in a
graph $G(V,E)$ and a parameter $r>0$. It begins by handling the special cases
for the vertex sets $V$ and $S$. When $V=\emptyset$ or $S=\emptyset$, it
directly returns an empty set. When $V\not=\emptyset$ and $S$ contains only
one vertex $u$, it includes the ball $ball_{V}(u,r)$ of round-trip radius $r$
around $u$ into the returned cover $C$. Otherwise, it calls Estimate-In-Out-
Balls (Algorithm 2) to get estimation for the sizes of the in-balls and out-
balls around every vertex $v\in V$ with radius $c\cdot r$, where $c$ is a
sufficiently large constant. If there is a vertex $u$ that can reach and be
reachable from many vertices, the algorithm directly includes its ball $B$ of
round-trip radius randomly picked from $[2c\cdot r,2(c+1)\cdot r]$ into the
cover $C$, and then recurses on the remaining graph $G(V-B)$. Otherwise, the
algorithm applies Cluster-Out(-In) (Algorithm 1) to partition the graph into
clusters and then recurses on each of the clusters. By proving that for each
recursion in either case above the graph vertex size is reduced by at least a
constant factor, we have that there are at most logarithmic levels of
recursions. Then by union bound we can reason the probability of vertex pairs
of interest at bounded round-trip distance in the same ball over all
recursions.

######  Theorem 5.

For a graph $G(V,E)$, an $s$-sized source vertex set $S\subseteq V$ and a
parameter $r>0$, Algorithm 3 constructs a collection $C$ of balls such that,
(1) for every $u\in S,v\in V$ at round-trip distance at most $R$, they are in
the same ball of $C$ with probability at least $exp((-6R/r)\log n\log s)$;
(2) each ball in $C$ has round-trip radius $O(r)$ w.h.p;
(3) each vertex $v\in V$ is contained in at most one ball of $C$.
Furthermore, the algorithm runs in time $O(m\log^{3}n)$.

###### Proof.

We first define notations we will use in the proof. We will use $G$ and $V$ to
denote the original graph and its vertex set respectively, and use
$G(V^{\prime})$ and $V^{\prime}$ to denote the graph before each invocation of
Algorithm 1 or 2 and its vertex set respectively. Obviously
$V^{\prime}\subseteq V$. For a chosen sufficiently large constant $c\geq 1$, a
single call of Algorithm 2 yields properties in Corollary 1 w.h.p. Similarly,
a single call of Algorithm 1 yields property (1) in Theorem 4 w.h.p.
Therefore, by the union bound, the event that all calls of Algorithms 1 and 2
yield the properties in Theorem 4 and Corollary 1 happens w.h.p. and we assume
this happens in the proof.

Conditioning on the above event, we prove that the algorithm never fails and
terminates through the exit in Line 14 when the if-test in Line 12 is true, or
otherwise the exit in Line 26. For the former case, let $u$ be such a vertex
in $U_{Out}$ $\cap$ $U_{In}$. According to Corollary 1, we have

$|out\text{-}ball_{V^{\prime}}(u,c\cdot
r)|\geq(3/4-1/8)\cdot|V^{\prime}|=5/8\cdot|V^{\prime}|.$

Similarly, $|in$-$ball_{V^{\prime}}(u,c\cdot r)|\geq 5/8\cdot|V^{\prime}|$.
Then the size of their intersection satisfies that

$|out\text{-}ball_{V^{\prime}}(u,cr)\cap
in\text{-}ball_{V^{\prime}}(u,cr)|\geq 1/4\cdot|V^{\prime}|.$

This implies that $|U_{Out}$ $\cap$ $U_{In}|\geq 1/4\cdot|V|$ and the failure
in Line 14 would not occur.

For the latter case (when the if-test in Line 12 fails), we have either
$|U_{Out}|\leq 1/2\cdot|V^{\prime}|$ or $|U_{In}|\leq 1/2\cdot|V^{\prime}|$.
Otherwise, their intersection must not be empty. We assume w.l.o.g. that
$|U_{Out}|\leq 1/2\cdot|V^{\prime}|$ and thus the algorithm Cluster-Out is
performed (in Line 21). According to Corollary 1 and property (1) of Theorem
4, we have for every $1\leq i\leq d-1$,

$|V_{i}|\leq(3/4+1/8)\cdot|V^{\prime}|=7/8\cdot|V^{\prime}|.$

Note that we use $V^{\prime}-U_{Out}$ as the centering vertices when calling
Cluster-Out. By property (2) of Theorem 4, the last cluster $V_{d}$ has size
at most

$|V_{d}|=|V^{\prime}|-|V^{\prime}-U_{Out}|\leq|U_{Out}|\leq
1/2\cdot|V^{\prime}|.$

Therefore, all clusters have size at most $7/8\cdot|V^{\prime}|$ and the
failure in Line 26 would not occur.

We now prove each of the three properties, staring from property (2). By the
ball constructions in Lines 8 and 18 and the fact that properties of Theorem 4
and Corollary 1 happen w.h.p., each ball has round-trip radius $O(r)$ in
$G(V^{\prime})$ w.h.p. Then each ball has round-trip radius $O(r)$ in $G$
w.h.p. because $V^{\prime}$ is a subset of $V$. Property (3) can be easily
verified by construction.

Next we prove property (1). In the algorithm, only Lines 18 and 31 can
separate two vertices into different balls. In Line 31, the probability of not
separating $u\in S,v\in V$ at round-trip distance at most $R$ in different
balls, if they have not been separated before, is at least $exp(-R/r\cdot\log
s)$, according to Theorem 4. In Line 18, the probability is at least

$1-R/2r\geq exp(-R/r\cdot\log n)\geq exp(-R/r\cdot\log s).$

Note that in Lines 18 and 31, the sizes of $V^{\prime}$ are multiplied by at
most 7/8 and 3/8, respectively. Therefore, the total levels of recursions can
be at most $\lceil\log_{7/8}|V|\rceil$. Then the probability of not separating
$u$ and $v$ in different balls over all recursions is at least

$(exp(-R/r\log s))^{\lceil\log_{7/8}n\rceil}\geq exp((-6R/r)\log n\log s).$

The running time $O(m\log^{3}n)$ follows because the total levels of
recursions is $O(\log n)$ and the running time of each recursion is dominated
by the running time of Estimate-In-Out-Balls (Algorithm 2)
$O(m\epsilon^{-2}\log^{2}n)$. ∎

The main algorithm for constructing source-wise round-trip covers is presented
in Algorithm 4. Given a source vertex set $S$ in a graph $G$, a stretch
parameter $k$ and a round-trip radius $R$, the union of the collection of
balls obtained by $\widetilde{O}(s^{1/k})$ invocations of RecursiveCover
(Algorithm 3) is an $S$-sourcewise round-trip cover of $G$ w.h.p. Executing
RecursiveCover for $\widetilde{O}(s^{1/k})$ times suffices to ensure that the
resulting collection of balls is the desired source-wise round-trip cover
w.h.p.

Algorithm 4 SWRT-Cover$(G(V,E),k,R,S)$

0: $G(V,E)$, a source vertex set $S$, an integer $k>1$, and a parameter $R>0$

0: An $S$-sourcewise $(O(k\log n),R)$-cover of $G$

1: $r\leftarrow 6Rk\log n$;

2: Let $c\geq 1$ be a sufficiently large constant;

3: $C\leftarrow\emptyset$;

4: for $1\leq i\leq c\cdot\lceil s^{1/k}\rceil\cdot\lceil\log n\rceil]$ do

5: $C\leftarrow C$ $\cap$ RecursiveCover$(G,r,S)$;

6: end for

7: return $C$;

###### Proof.

(_Theorem 2._) By property (1) of Theorem 5, we have that for every $u\in
S,v\in V$ at round-trip distance at most $R$, the probability that they are in
the same ball in a single invocation of RecursiveCover is at least

$exp((-6R/r)\log n\log s)=exp((-1/k)\log s)=s^{-1/k}.$

The probability that $u$ and $v$ are in a ball $B\in C^{\prime}$ for a
structure $C^{\prime}$ constructed by $\lceil s^{1/k}\rceil$ invocations of
RecursiveCover is at least

$1-(1-1/s^{1/k})^{s^{1/k}}=1-exp(-1).$

Then the probability that $u$ and $v$ are in a ball $B\in C$ for a structure
$C$ constructed by $c\cdot\lceil s^{1/k}\rceil\cdot\lceil\log n\rceil$
invocations of RecursiveCover is at least

$1-(exp(-1))^{c\cdot\lceil\log n\rceil}\geq 1-1/n^{c}.$

For a sufficiently large constant $c$, the event that they are in a ball $B\in
C$ happens w.h.p.

According to property (2) of Theorem 5, each ball $B\in C$ has round-trip
radius at most $O(r)=O(Rk\log n)$ w.h.p. Therefore, the constructed collection
of balls $C$ is an $S$-sourcewise $(O(k\log n),R)$-cover w.h.p. By property
(3) of Theorem 5, each vertex is contained in $O(s^{1/k}\log n)$ balls of $C$.
∎

##  4 Removing the Dependence on the Edge Weights

In this section, we remove the dependence on the edge weights for the bounds
in Theorem 3 in order to obtain our main theorem, Theorem 1. Although there
has been a technique [26, 20, 31] that can remove the dependence on the edge
weights for standard round-trip spanners, it is still not clear whether and
how it can be adapted to the source-wise setting. In this paper, we show an
adaptation of the technique and rigorously prove its correctness. Similar to
[26, 20, 31], the intuition is that we do not need to consider all edges of
the original graph when constructing a source-wise $(O(k\log n),R)$-roundtrip
cover for a fixed round-trip radius $R$. We introduce contraction operations
in the source-wise case so that when exponentially increasing round-trip
distances are considered, the number of times that each edge is presented is
bounded by a logarithm in the number of vertices.

We first describe contraction operations for the standard setting as defined
in [26], and then show the adapted contractions in the source-wise setting.
For a graph $G(V,E)$ and two real numbers $x_{L}$ and $x_{R}$, $G$ is
contracted to $[x_{L},x_{R}]$ by, (1) merging vertices in any strongly
connected component (or for short _SCC_) with maximum edge weight at most
$x_{L}$ into a single vertex; (2) removing all edges of weights larger than
$x_{R}$; (3) removing all edges that _do not_ participate in any _SCC_ with
maximum edge weight at most $x_{R}$; (4) removing all vertices with no edge
after the above steps. In the source-wise setting, we have a source vertex set
$S\subseteq V$ in the original graph $G$. During the contraction, we can
construct a new source vertex set $S^{\prime}$ together with the contracted
graph by adding additional work in some of the contraction steps.
Specifically, $S^{\prime}$ is first initialized to the original sources $S$.
In Step (1), if a source vertex $u$ participates in an _SCC_ and gets merged
into a single vertex $u^{\prime}$, replace $u$ by $u^{\prime}$ in
$S^{\prime}$. In Step (4), if a source vertex $u$ has no edge (after all the
above steps) and gets removed, remove $u$ from $S^{\prime}$.

We will use the following definition and lemma in our proof shortly.

######  Definition 2.

(Definition 5.6 from [26]) For two vertices $u$ and $v$ in a graph $G$, their
$L_{\infty}$-roundtrip distance, $d_{G}^{\infty}(u,v)$, is defined as the
minimum value of $d$ such that there is a (simple) cycle with maximum edge
weight $d$ containing $u$ and $v$.

######  Lemma 2.

(Lemma 5.7 from [26]) For a graph $G$ and every $t\in\mathbb{Z}$, let
$G^{(t)}$ be $G$ contracted to $[2^{t}/n,2^{t}]$. The total number of edges
and vertices in all non-empty $G^{(t)}$ are $O(m\log n)$ and $O(n\log n)$,
respectively.

We will use the algorithm, Roundtrip-$L_{\infty}$-Spanner$(\cdot)$, in [26] to
construct, for a digraph $G$, a tree for efficient computations of
$d_{G}^{\infty}(u,v)$ for each edge $(u,v)$ in $G$, and a sparse edge set
preserving pair-wise $L_{\infty}$-roundtrip distances in $G$. The following
lemma summarizes properties of the algorithm.

######  Lemma 3.

(Lemma 5.9 from [26]) For a directed graph $G(V,E)$,
Roundtrip-$L_{\infty}$-Spanner$(G)$ constructs,
(1) an $O(n)$-sized edge set $H\subseteq E$ such that for any vertex pair
$u,v$ contained in a cycle with maximum edge weight $R$ in $G$, there is a
cycle containing $u$ and $v$ with maximum edge weight $R$ in
$G^{\prime}(V,H)$;
(2) a tree $T$ such that for every $u,v\in V\times V$, the label of their
lowest common ancestor in $T$ is $d_{G}^{\infty}(u,v)$.
Moreover, the algorithm runs in $O(m\log n)$ time.

######  Corollary 2.

Given the tree $T$ obtained in Lemma 3, all non-empty $G^{(t)}$ and their
source vertex sets $S^{(t)}$ can be computed in linear time.

###### Proof.

Consider an edge $e=(u,v)\in E$ that is an edge in $G^{(t)}$. Because $e$ is
kept in $G^{(t)}$, we have $d_{G}^{\infty}(u,v)>2^{t}/n$. Also, $e$ must
participate in an _SCC_ with maximum edge weight $2^{t}$ in $G$. By
definition, it means $d_{G}^{\infty}(u,v)\leq 2^{t}$. Combining the two
inequalities we have

$\log_{2}d_{G}^{\infty}(u,v)\leq t<\log_{2}d_{G}^{\infty}(u,v)+\log n.$ (1)

It means that the edge $e$ is presented only in $G^{(t)}$ for $t$ in the above
interval.

Consider a vertex $u$ presented in $G^{(t)}$. By construction, we have $u$
belongs to an _SCC_ with maximum edge weight $2^{t}$ in $G$. Then for
$t^{\prime}\geq t+\log_{2}n$, $u$ will be merged into an _SCC_ in
$G^{(t^{\prime})}$. That is, $u$ only appears in at most $\log_{2}n$ graphs
$G^{(t)}$.

Suppose initially $G^{(t)}=(V,\emptyset)$ for each $t\in\mathbb{Z}$. Given the
tree $T$ computed in Lemma 3, we can calculate $d_{G}^{\infty}(u,v)$ for every
edge $e=(u,v)$ by executing a lowest common ancester query between $u$ and $v$
in $T$ using constant time. We can then include $e$ into $G^{(t)}$ for every
$\log_{2}d_{G}^{\infty}(u,v)\leq t<\log_{2}d_{G}^{\infty}(u,v)+\log n$
according to Inequality (1). Next, with the knowledge that each vertex $u$ can
only appear in at most $\log_{2}n$ graphs $G^{(t)}$, we merge vertices in an
_SCC_ when necessary. Finally, all $G^{(t)}$ can be obtained by removing all
vertices with no edge. Similarly, all contracted source vertex sets $S^{(t)}$
can also be calculated in the vertex merging and removing steps. All these
steps work in linear time. ∎

Now we are ready to present the algorithm (Algorithm 5) for constructing
source-wise round-trip spanners of size independent of the maximum edge
weight. Consider a source vertex set $S\subseteq V$ in a digraph $G(V,E)$. We
first call Roundtrip-$L_{\infty}$-Spanner on $G$ to construct an edge set
$H_{1}$ and a tree $T$. Next, for every $t\in\mathbb{Z}$, we construct a
contracted graph $G^{(t)}$ and its corresponding source vertex set $S^{(t)}$
with the help of $T$, as shown in Corollary 2. After that, for every non-empty
$G^{(t)}$, we call SWRT-Cover (Algorithm 4) with parameters $k,2^{t}$ and
$S^{(t)}$ to get a round-trip cover $C$. For each ball $B\in C$, we include
edges in $RT$-$Tree(B)$ into the edge set $H$. Finally, $G^{\prime}(V,H)$ is
returned as the source-wise round-trip spanner.

Algorithm 5 SWRT-Spanner$(G(V,E),k,S)$

0: $G(V,E)$, a vertex set $S$, and an integer $k>1$

0: An $S$-sourcewise $O(k\log n)$-roundtrip spanner of $G$

1: $(H_{1},T)\leftarrow$Roundtrip-$L_{\infty}$-Spanner$(G)$;

2: $H\leftarrow H_{1}$;

3: For every $t\in\mathbb{Z}$, construct $G^{(t)}$ and its corresponding
source vertex set $S^{(t)}$ with the help of $T$;

4: for each non-empty $G^{(t)}$ do

5: $C\leftarrow$SWRT-Cover$(G^{(t)},k,2^{t},S^{(t)})$;

6: $H\leftarrow H\cup\cup_{B\in C}RT$-$Tree(B)$;

7: end for

8: return $G^{\prime}(V,H)$;

###### Proof.

(_Theorem 1_) According to Lemma 2, both numbers of edges and vertices in all
non-empty $G^{(t)}$ are increased by a factor of $\log n$. Then according to
Theorem 2 and Corollary 2, the number of edges in the spanner and the running
time are $O(ns^{1/k}\log^{2}n)$ and $O(ms^{1/k}\log^{5}n)$, respectively.

It remains to prove that the stretch factor is $O(k\log n)$. Consider vertices
$u,v\in S\times V$ at round-trip distance $R$ in $G$ such that $2^{t-1}\leq
R<2^{t}$. Suppose vertices $u^{\prime}$ and $v^{\prime}$ are the corresponding
vertex of $u$ and $v$ in the contracted graph $G^{(t)}$, respectively. By the
definition of source-wise round-trip covers, in the structure $\cup_{B\in
C}RT$-$Tree(B)$ for an $S$-sourcewise $(O(k\log n),2^{t})$-cover $C$, there
must exist a round-trip path $P^{\prime}(u^{\prime},v^{\prime})$ of distance
$O(k2^{t}\log n)$ between $u^{\prime}$ and $v^{\prime}$ in $G^{(t)}$.
According to Lemma 3, for any _SCC_ with maximum edge weight $w^{\prime}$ in
$G$, there must exist a corresponding _SCC_ with maximum edge weight
$w^{\prime}$ in the graph $G_{1}(V,H_{1})$, where $H_{1}$ is the sparse edge
set constructed by Roundtrip-$L_{\infty}$-Spanner in Line 1. Therefore, we can
uncontract $P^{\prime}(u^{\prime},v^{\prime})$ into a new round-trip path
$P(u,v)$ in $G^{\prime}(V,H)$, by first uncontracting every vertex resulted
from vertex merging back to the vertices of its _SCC_ in $G$, and then adding
edges of the corresponding _SCC_ in $H_{1}$ to $P$. This unpacking process
enlarges the distance of $P^{\prime}$ by at most

$w^{\prime}\cdot n\leq 2^{t}/n\cdot n=2^{t},$

where the first inequality holds because $P^{\prime}$ is a path in $G^{(t)}$.
Therefore, the distance of $P$ is $O((k+1)2^{t}\log n)=O(kR\log n)$ as
$2^{t-1}\leq R$. This complete the proof. ∎

##  5 Conclusion and Future Work

In this paper, we propose a fast algorithm for constructing source-wise round-
trip spanners in weighted directed graphs. Specifically, given an $n$-vertex
$m$-edge graph $G(V,E)$, an $s$-sized source vertex set $S\subseteq V$ and an
integer $k>1$.we propose a fast algorithm that in time $O(ms^{1/k}\log^{5}n)$
constructs an $S$-sourcewise round-trip spanner of stretch $O(k\log n)$ and
size $O(ns^{1/k}\log^{2}n)$ w.h.p. Essentially we propose a source-wise graph
partitioning algorithm which takes an integer $s$ and a graph $G$ as input,
partitions $G$ into clusters of bounded radius, and guarantees that for every
$u,v\in S\times V$ at small round-trip distance, the probability of they are
in different clusters is small. We then rigorously prove that the recursive
algorithm for constructing standard round-trip spanners [26] can be
generalized to the source-wise setting. Compared to the fast algorithms for
constructing all-pairs round-trip spanners [26, 12], our algorithm improves
the running time and the size of the spanner when $k$ is super-constant.
Compared with the existing algorithm for constructing source-wise round-trip
spanners [36], the developed algorithm significantly improves their
construction time $\Omega(\min\\{ms,n^{\omega}\\})$ to nearly linear
$O(ms^{1/k}\log^{5}n)$ at the expense of an extra factor $\log n$ in the
stretch. As the future work, we will study deterministic constructions of
source-wise round-trip spanners and how to improve the $\log n$ factor in the
stretch while preserving the nearly linear running time. Note that such
improvements in the stretch have been achieved for all-pairs spanners [12]. It
is also interesting to study general _pair-wise_ round-trip spanners and
investigate whether efficient algorithms exist when there is no structure in
the vertex pairs, e.g., $S\times V$ in the source-wise case.

## References

  * [1] A. Abboud and G. Bodwin.  The 4/3 additive spanner exponent is tight.  In Proceedings of STOC Conference, pages 351–361, 2016.
  * [2] Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Stephen Kobourov, and Richard Spence.  Weighted Additive Spanners.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 401–413, 2020.
  * [3] Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, and Richard Spence.  Graph spanners: a tutorial review.  Computer Science Review, 37, 2020.
  * [4] D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani.  Fast estimation of diameter and shortest paths (without matrix multiplication).  SIAM Journal on Computing, 28(4):1167–1181, 1999.
  * [5] Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, and Christian Wulff-Nilsen.  Constructing Light Spanners Deterministically in Near-Linear Time.  In Proceedings of ESA Conference, pages 4:1–4:15, 2019.
  * [6] I. Althofer, G. Das, D.P. Dobkin, D. Joseph, and J. Soares.  On sparse spanners of weighted graphs.  Discrete Computational Geometry, 9:81–100, 1993.
  * [7] S. Baswana, T. Kavitha, K. Mehlhorn, and S. Pettie.  Additive spanners and $(\alpha,\beta)$-spanners.  ACM Transactions on Algorithms, 7(1), 2010.
  * [8] G. Bodwin.  Linear size distance preservers.  In Proceedings of SODA Conference, pages 600–615, 2017.
  * [9] Greg Bodwin, Michael Dinitz, and Caleb Robelle.  Optimal Vertex Fault-Tolerant Spanners in Polynomial Time.  In To appear in Proceedings of SODA Conference, 2021.
  * [10] Ruoxu Cen, Ran Duan, and Yong Gu.  Roundtrip Spanners with $(2k-1)$ Stretch.  In Proceedings of ICALP Conference, pages 24:1–24:11, 2020.
  * [11] S. Chechik.  New additive spanners.  In Proceedings of SIAM SODA Conference, pages 498–512, 2013.
  * [12] S. Chechik, Y. P. Liu, O. Rotem, and A. Sidford.  Constant girth approximation for directed graphs in subquadratic time.  In Proceedings of STOC Conference, pages 1010–1023, 2020.
  * [13] E. Cohen.  Size-estimation framework with applications to transitive closure and reachability.  Journal of Computer and System Sciences, 55(3):441–453, 1997.
  * [14] D. Coppersmith and M. Elkin.  Sparse source-wise and pair-wise preservers.  SIAM Journal on Discrete Mathematics, 20(2):463–501, 2006.
  * [15] L. Cowen and C. Wagner.  Compact roundtrip routing in digraphs.  In Proceedings of SIAM SODA Conference, pages 885–886, 1999.
  * [16] L. Cowen and C. Wagner.  Compact roundtrip routing in directed graphs.  In Proceedings of ACM PODC Conference, pages 51–59, 2000.
  * [17] M. Cygan, F. Grandoni, and T. Kavitha.  On pairwise spanners.  In Proceedings of STACS Conference, pages 209–220, 2013.
  * [18] Mina Dalirrooyfard and Virginia Vassilevska Williams.  Conditionally optimal approximation algorithms for the girth of a directed graph.  In Proceedings of ICALP Conference, pages 35:1–35:20, 2020.
  * [19] M. Elkin and D. Peleg.  $(1+\epsilon,\beta)$-spanner constructions for general graph.  SIAM Journal on Computing, 33(3):608–631, 2004.
  * [20] A. Ene, G. Miller, J. Pachocki, and A. Sidford.  Rounting under balance.  In Proceedings of STOC Conference, pages 598–611, 2016.
  * [21] P. Erdos.  Extremal problems in graph theory.  Theory of Graphs and Its Applications, pages 29–36, 1964.
  * [22] T. Kavitha.  New pairwise spanners.  In Proceedings of STACS Conference, pages 513–526, 2015.
  * [23] T. Kavitha and N.M. Varma.  Small stretch pairwise spanners.  In Proceedings of ICALP Conference, pages 601–612, 2013.
  * [24] G. Miller, R. Peng, and S. Xu.  Parallel graph decompositions using random shifts.  In Proceedings of STOC Conference, pages 193–203, 2013.
  * [25] J. Orlin.  An $o(nm)$ time algorithm for finding the min length directed cycle in a weighted graph.  In Proceedings of SODA Conference, pages 1866–1879, 2017.
  * [26] J. Pachocki, L. Roditty, A. Sidford, R. Tov, and V. Williams.  Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners.  In Proceedings of SODA Conference, pages 1374–1392, 2018.
  * [27] M. Parter.  Bypassing Erdos’ girth conjecture: hybrid stretch and sourcewise spanners.  In Proceedings of ICALP Conference, pages 608–619, 2014.
  * [28] D. Peleg and A.A. Schaffer.  Graph spanners.  Journal of Graph Theory, 13(1):99–116, 1989.
  * [29] S. Pettie.  Low distortion spanners.  ACM Transactions on Algorithms, 6(1), 2009.
  * [30] I. Roditty, M. Thorup, and U. Zwick.  Deterministic constructions of approximate distance oracles and spanners.  In Proceedings of ICALP Conference, pages 261–272, 2005.
  * [31] I. Roditty, M. Thorup, and U. Zwick.  Roundtrip spanners and roundtrip routing in directed graphs.  ACM Transactions on Algorithms, 4(3), 2008.
  * [32] M. Thorup and U. Zwick.  Approximate distance oracles.  Journal of the ACM, 52(1):1–24, 2005.
  * [33] M. Thorup and U. Zwick.  Spanners and emulators with sublinear distance errors.  In Proceedings of SIAM SODA Conference, pages 802–809, 2006.
  * [34] V.V. Williams and R. Williams.  Subcubic equivalences between path, matrix and triangle problems.  In Proceedings of FOCS Conference, pages 645–654, 2010.
  * [35] D.P. Woodruff.  Additive spanners in nearly quadratic time.  In Proceedings of ICALP Conference, pages 463–474, 2010.
  * [36] C. Zhu and K. Lam.  Source-wise round-trip spanners.  Information Processing Letters, 124(C):42–45, 2017.
  * [37] C. Zhu and K. Lam.  Deterministic improved round-trip spanners.  Information Processing Letters, 127:57–60, 2018.


$\lambda^{r_{i}}(v_{i})^{\ell}u_{i}v_{i+1}^{\ell}$. Let
$\hat{u}_{i}=x_{i}u_{i}y_{i}$ be the corresponding decomposition. Then $\beta$
has to map $x_{i}$ into $\lambda^{r_{i}}(v_{i})^{\ell}$ and $y_{i}$ into
$v_{i+1}^{\ell}$. In particular, we have
$x_{i}\in\mathord{\downarrow}_{\preceq_{d}}\lambda^{r_{i}}(v_{i})^{*}$ and
$y_{i}\in\mathord{\downarrow}_{\preceq_{d}}v_{i+1}^{*}$. This completes the
proof of the claim and hence the Lemma. ∎

###  O.4. Proof of Proposition 6.2

######  Lemma O.8.

Let $\mathcal{A}$ be an automaton with $\leq m$ states and let $d$ be a
multiple of $m^{3}!$. Moreover, let $\pi_{d}(v)\leq m^{2}$ and let
$u\in\mathord{\downarrow}_{\preceq_{d}}v^{[r]}$ be accepted by $\mathcal{A}$
such that $|u|\geq m\cdot\pi_{d}(v)$. Then there is a
$u^{\prime}\in\mathord{\downarrow}_{\preceq_{\ell\cdot
d}}(v^{\ell})^{[r^{\prime}]}$ in $L(\mathcal{A})$ such that
$r^{\prime}=r+(\ell-1)d$ and $|u^{\prime}|=|u|+(\ell-1)d$.

###### Proof.

Since $|u|\geq m\cdot\pi_{d}(v)$, $u$ begins with at least $|u|/\pi_{d}(v)\geq
m$ factors of length $\pi_{d}(v)$. Consider the run of $\mathcal{A}$ on $u$.
Since $\mathcal{A}$ has at most $m$ states, we can decompose $u=fgh$ such that
$g$ is a contiguous block of $k\leq m$ factors of length $\pi_{d}(v)$ and $g$
is read on a cycle. Since $|g|=k\cdot\pi_{d}(v)\leq m^{3}$, $|g|$ divides $d$.
Let $u^{\prime}=fg^{1+(\ell-1)d/|g|}h$. Then according to Lemma O.4, we have
$u^{\prime}\in\mathord{\downarrow}_{\preceq_{d}}v^{[r]}$. Therefore,
$\kappa_{d}(u^{\prime})\subseteq\kappa_{d}(v)$. This implies

$\kappa_{\ell\cdot d}(u^{\prime})\subseteq\kappa_{\ell\cdot
d}(v)\subseteq\kappa_{\ell\cdot d}(v^{\ell}).$

Moreover, note that $|u^{\prime}|=|u|+(\ell-1)d\equiv
r+(\ell-1)d=r^{\prime}\pmod{\ell\cdot d}$ and thus
$u^{\prime}\in\mathord{\downarrow}_{\preceq_{d}}(v^{\ell})^{[r^{\prime}]}$. ∎

######  Lemma O.9.

Let $\mathcal{A}$ be an automaton with $\leq m$ states and let $d$ be a
multiple of $m^{3}!$. Moreover, let $v\in(\Sigma^{d})^{*}$ with
$\pi_{d}(v)\leq m^{2}$. If $u\in L(\mathcal{A})$ with
$w\preceq_{d}u\in\mathord{\downarrow}_{\preceq_{d}}v^{[r]}$, then there is a
$u^{\prime}\in L(\mathcal{A})$ with $w\preceq_{\ell\cdot
d}u^{\prime}\in\mathord{\downarrow}_{\preceq_{\ell\cdot d}}(v^{\ell})^{[r]}$

###### Proof.

Since $w\preceq_{d}u$, we can write $u=u_{0}w_{1}u_{1}\cdots w_{n}u_{n}$,
where $w=w_{1}\cdots w_{n}$ and $w_{1},\ldots,w_{n}\in\Sigma$, and
$u_{i}\in(\Sigma^{d})^{*}$. Since
$u\in\mathord{\downarrow}_{\preceq_{d}}v^{[r]}$, we have
$\kappa_{d}(u)\subseteq\kappa_{d}(v)$ and hence
$u_{i}\in\mathord{\downarrow}_{\preceq_{d}}\lambda^{i}(v)^{*}$ for
$i\in[0,n]$.

For each $i\in[0,n]$, we construct $u^{\prime}_{i}$ as follows. Consider the
run of $\mathcal{A}$ on $u$ and suppose it reads $u_{i}$ from state $p_{i}$ to
state $q_{i}$.

  * •

If $u_{i}$ is empty, then $u^{\prime}_{i}=u_{i}$. Note that then of course
$u^{\prime}_{i}\in\mathord{\downarrow}_{\preceq_{\ell\cdot
d}}\lambda^{i}(v^{\ell})^{*}$.

  * •

If $u_{i}$ is non-empty, then we split $u_{i}$ in $|u_{i}|/d$ factors of
length $d$ and apply to each factor Lemma O.8. This yields a word a word
$u^{\prime}_{i}$ such that
$u^{\prime}_{i}\in\mathord{\downarrow}_{\preceq_{\ell\cdot
d}}(\lambda^{i}(v)^{\ell})^{*}$ and so that $u^{\prime}_{i}$ can be read from
state $p_{i}$ to $q_{i}$. Moreover, we have $|u^{\prime}_{i}|$ is a multiple
of $\ell\cdot d$. Since $\lambda^{i}(v)^{\ell}=\lambda^{i}(v^{\ell})$, we have
$u^{\prime}_{i}\in\mathord{\downarrow}_{\preceq_{\ell\cdot
d}}\lambda^{i}(v^{\ell})^{*}$.

Therefore, the word $u^{\prime}=u^{\prime}_{0}w_{1}u^{\prime}_{1}\cdots
w_{n}u^{\prime}_{n}$ is accepted by $\mathcal{A}$, belongs to
$\mathord{\downarrow}_{\preceq_{\ell\cdot d}}(v^{\ell})^{[r]}$ and satisfies
$w\preceq_{\ell\cdot d}u^{\prime}$. ∎

######  Lemma O.10.

Let $\mathcal{A}$ be an automaton with $\leq m$ states and and let $d$ be a
multiple of $2m^{3}!$. Moreover, let $v_{i}\in(\Sigma^{d})^{*}$ with
$\pi_{d}(v_{i})\leq m^{2}$ for $i=1,2$. If $u\in L(\mathcal{A})$ with
$u\in\mathord{\downarrow}_{\preceq_{d}}v_{1}^{*}v_{2}^{*}$, then there is a
$u^{\prime}\in L(\mathcal{A})$ with
$u^{\prime}\in\mathord{\downarrow}_{\preceq_{\ell\cdot
d}}(v_{1}^{\ell})^{*}(v_{2}^{\ell})^{*}$

###### Proof.

Let $K=\mathord{\downarrow}_{\preceq_{d}}v_{1}^{*}v_{2}^{*}$. Observe that $K$
consists precisely of the words of the form $u=x_{1}\cdots x_{p}sty_{1}\cdots
y_{q}$, where for some $r\in[0,d-1]$,

  * •

$x_{i}\in\mathord{\downarrow}_{\preceq_{d}}v_{1}^{*}$ and $x_{i}\in\Sigma^{d}$
for $i\in[1,p]$,

  * •

$s\in\mathord{\downarrow}_{\preceq_{d}}v_{1}^{[r]}$ and $|s|=r$,

  * •

$t\in\mathord{\downarrow}_{\preceq_{d}}\lambda^{r}(v_{2})^{[d-r]}$, and
$|t|=d-r$, and

  * •

$y_{i}\in\mathord{\downarrow}_{\preceq_{d}}v_{2}^{*}$ and $y_{i}\in\Sigma^{d}$
for $i\in[1,q]$.

On the one hand, all such words belong to
$\mathord{\downarrow}_{\preceq_{d}}v_{1}^{*}v_{2}^{*}$: The parts $s$ and $t$
arise when dropping length-$d$ blocks on the border between $v_{1}^{*}$ and
$v_{2}^{*}$. On the other hand, by induction on the number of deleted
length-$d$ blocks, it follows that any word in
$\mathord{\downarrow}_{\preceq_{d}}v_{1}^{*}v_{2}^{*}$ is of that shape.

Since $|s|+|t|=d$, we have either $|s|\geq d/2$ or $|t|\geq d/2$. We treat the
case that $|s|\geq d/2$, the other case is analogous.

We apply Lemma O.8 to each factor $x_{1},\ldots,x_{p},s,y_{1},\ldots,y_{q}$.
Note that this is possible because each of these words has length either
exactly $d$ or $\geq d/2$ and we have $\geq d/2\geq m^{3}!\geq m^{3}\geq
m\cdot\pi_{d}(v_{i})$ for $i=1,2$. This yields words
$x^{\prime}_{1},\ldots,x^{\prime}_{p},s^{\prime},y^{\prime}_{1},\ldots,y^{\prime}_{q}$
such that

  * •

$x^{\prime}_{i}\in\mathord{\downarrow}_{\preceq_{\ell\cdot
d}}(v_{1}^{\ell})^{[0]}$ for $i\in[1,p]$,

  * •

$s^{\prime}\in\mathord{\downarrow}_{\preceq_{\ell\cdot
d}}(v_{1}^{\ell})^{[r^{\prime}]}$, where $r^{\prime}=r+(\ell-1)d$,

  * •

$y^{\prime}_{i}\in\mathord{\downarrow}_{\preceq_{\ell\cdot
d}}(v_{2}^{\ell})^{[0]}$ for $i\in[1,q]$,

  * •

$\mathcal{A}$ accepts $u^{\prime}=x^{\prime}_{1}\cdots
x^{\prime}_{p}s^{\prime}ty^{\prime}_{1}\cdots y^{\prime}_{q}$.

Recall that
$t\in\mathord{\downarrow}_{\preceq_{d}}\lambda^{r}(v_{2})^{[d-r]}$. This means
$\kappa_{d}(t)\subseteq\kappa_{d}(\lambda^{r}(v_{2}))$ and hence

$\kappa_{d}(t)\subseteq\kappa_{d}(\lambda^{r}(v_{2})^{\ell})=\kappa_{d}(\lambda^{r}(v_{2}^{\ell}))$

(recall that $\lambda^{r}(w)^{\ell}=\lambda^{r}(w^{\ell})$ for every word
$w$). Therefore, we also have

(4) $\kappa_{\ell\cdot d}(t)\subseteq\kappa_{\ell\cdot
d}(\lambda^{r}(v_{2}^{\ell})).$

Note that since $\pi_{\ell\cdot d}(v_{2}^{\ell})=\pi_{d}(v_{2})$ divides $d$,
we can rotate the word $v_{2}^{\ell}$ by a multiple of $d$ without changing
its image under $\kappa_{\ell\cdot d}(\cdot)$. Hence

$\kappa_{\ell\cdot d}(\lambda^{r}(v_{2}^{\ell}))=\kappa_{\ell\cdot
d}(\lambda^{r+(\ell-1)d}(v_{2}^{\ell}))$

Together with eq. 4, we may conclude that $t$ belongs to
$\mathord{\downarrow}_{\preceq_{\ell\cdot
d}}(\lambda^{r+(\ell-1)d}(v_{2}^{\ell}))^{[d-r]}$ according to Lemma O.6.
Therefore, the above characterization of $K$, adapted to
$\mathord{\downarrow}_{\preceq_{\ell\cdot
d}}(v_{1}^{\ell})^{*}(v_{2}^{\ell})^{*}$, is satisfied for the word
$u^{\prime}$ and hence $u^{\prime}\in\mathord{\downarrow}_{\preceq_{\ell\cdot
d}}(v_{1}^{\ell})^{*}(v_{2}^{\ell})^{*}$. ∎

######  Lemma O.11.

Let $\mathcal{A}$ be a finite automaton with $\leq m$ states and let $d$ be a
multiple of $2m^{3}!$. If $u_{0}v_{1}^{[r_{1}]}u_{1}\cdots
v_{n}^{[r_{n}]}u_{n}$ is an irreducible extended loop pattern with
$\pi_{d}(v_{i})\leq m^{2}$ such that its ideal belongs to
$\mathsf{Adh}_{\preceq_{d}}(L(\mathcal{A}))$, then for each
$\ell\in\mathbb{N}$, the ideal

(5) $\mathord{\downarrow}_{\preceq_{\ell\cdot
d}}u_{0}(v_{1}^{\ell})^{[r_{1}]}u_{1}\cdots(v_{n}^{\ell})^{[r_{n}]}u_{n}$

belongs to $\mathsf{Adh}_{\preceq_{\ell\cdot d}}(L(\mathcal{A}))$.

###### Proof.

Since $u_{0}v_{1}^{[r_{1}]}u_{1}\cdots v_{n}^{[r_{n}]}u_{n}$ is irreducible
and its ideal belongs to $\mathsf{Adh}_{\preceq_{d}}(L(\mathcal{A}))$, we know
from Lemma 6.6 that the extended loop pattern is associated to
$L(\mathcal{A})$.

Let $I$ be the ideal in eq. 5. Let $w_{i}$ be the length-$r_{i}$ prefix of
$v_{i}$ for every $i\in[1,n]$.

In order to show that $I$ belongs to $\mathsf{Adh}_{\preceq_{\ell\cdot
d}}(L(\mathcal{A}))$, we have to exhibit for each $k\in\mathbb{N}$ a word
$w\in L(\mathcal{A})$ so that
$u_{0}(v_{1}^{\ell})^{k}w_{1}u_{1}\cdots(v_{n}^{\ell})^{k}w_{n}u_{n}\preceq_{\ell\cdot
d}w$ and $w\in I$.

Let $k\in\mathbb{N}$. Because of association, there is a word
$\bar{w}=\bar{u}_{0}\bar{v}_{1}\bar{u}_{1}\cdots\bar{v}_{n}\bar{u}_{n}\in
L(\mathcal{A})$ such that for every $i\in[1,n]$, we have
$v_{i}^{k\cdot\ell}w_{i}\preceq_{d}\bar{v}_{i}$ and
$\bar{v}_{i}\in\mathord{\downarrow}_{\preceq_{d}}v_{i}^{[r_{i}]}$. Moreover,
$\bar{u}_{0}=u_{0}$, $\bar{u}_{n}=u_{n}$, and for each $i\in[1,n-1]$:

  * •

If $u_{i}$ is not empty, then $\bar{u}_{i}=u_{i}$.

  * •

If $u_{i}$ is empty, then
$\bar{u}_{i}\in\mathord{\downarrow}_{\preceq_{d}}\lambda^{r_{i}}(v_{i})^{*}v_{i+1}^{*}$.

Consider the run of $\mathcal{A}$ on $\bar{w}$. Using Lemma O.9, we can choose
$\bar{v}^{\prime}_{i}$ such that $v_{i}^{k\cdot\ell}w_{i}\preceq_{\ell\cdot
d}\bar{v}^{\prime}_{i}$ and
$\bar{v}^{\prime}_{i}\in\mathord{\downarrow}_{\preceq_{\ell\cdot\ell}}(v_{i}^{\ell})^{[r_{i}]}$
and so that it has a run parallel to $\bar{v}_{i}$ in $\mathcal{A}$. Now
consider $\bar{u}_{i}$ for $i\in[0,n]$.

  * •

If $\bar{u}_{i}=u_{i}$, then choose $\bar{u}^{\prime}_{i}=\bar{u}_{i}=u_{i}$.

  * •

If $\bar{u}_{i}\neq u_{i}$, then $u_{i}$ is empty and
$\bar{u}_{i}\in\mathord{\downarrow}_{\preceq_{d}}\lambda^{r_{i}}(v_{i})^{*}v_{i+1}^{*}$.
Then we use Lemma O.10 to choose $\bar{u}^{\prime}_{i}$ such that
$\bar{u}^{\prime}_{i}$ has a run parallel to $\bar{u}_{i}$ in $\mathcal{A}$
and $\bar{u}^{\prime}_{i}\in\mathord{\downarrow}_{\preceq_{\ell\cdot
d}}(\lambda^{r_{i}}(v_{i}^{\ell}))^{*}(v_{i+1}^{\ell})^{*}$.

Now the resulting word
$w^{\prime}=\bar{u}^{\prime}_{0}\bar{v}^{\prime}_{1}\bar{u}^{\prime}_{1}\cdots\bar{v}^{\prime}_{n}\bar{u}^{\prime}_{n}$
is accepted by the automaton $\mathcal{A}$. This shows that the extended loop
pattern
$u_{0}(v_{1}^{\ell})^{[r_{1}]}u_{1}\cdots(v_{n}^{\ell})^{[r_{n}]}u_{n}$ is
associated to $L(\mathcal{A})$ and hence the ideal $I$ belongs to
$\mathsf{Adh}_{\preceq_{\ell\cdot d}}(L(\mathcal{A}))$. ∎

###### Proof of Proposition 6.2.

Suppose there is an ideal in the adherence
$\mathsf{Adh}_{\preceq_{d}}(L(\mathcal{A}_{i}))$ for $i=1,2$. By Lemma 6.5,
there is a loop pattern $u_{0}v_{1}u_{1}\cdots v_{n}u_{n}$ for
$\mathcal{M}_{d}$ such that the ideal
$I=\mathord{\downarrow}_{\preceq_{d}}u_{0}v_{1}^{*}u_{1}\cdots v_{n}^{*}u_{n}$
belongs to $\mathsf{Adh}_{\preceq_{d}}(L(\mathcal{A}_{i}))$ for $i=1,2$ and
$\pi_{d}(v_{i})\leq m^{2}$ for every $i\in[1,n]$. Using Lemma O.7, we can
construct an irreducible extended loop pattern

$\bar{u}_{0}\bar{v}_{1}^{[r_{1}]}\bar{u}_{1}\cdots\bar{v}_{n}^{[r_{n}]}\bar{u}_{n}$

that induces $I$ and satisfies $\pi_{d}(\bar{v}_{i})\leq m^{2}$ for
$i\in[1,n]$. Now Lemma O.11 tells us that the ideal

$\mathord{\downarrow}_{\preceq_{\ell\cdot
d}}\bar{u}_{0}(\bar{v}_{1}^{\ell})^{[r_{1}]}\bar{u}_{1}\cdots(\bar{v}_{n}^{\ell})^{[r_{n}]}\bar{u}_{n}$

belongs to $\mathsf{Adh}_{\preceq_{\ell\cdot d}}(L(\mathcal{A}_{i}))$ for
$i=1,2$. ∎

###  O.5. Proof of Proposition 6.7

###### Proof of Proposition 6.7.

Recall that the _Post Correspondence Problem_ asks, given two morphisms
$\alpha,\beta\colon\Sigma^{*}\to\\{1,2\\}^{*}$, whether there is a word
$w\in\Sigma^{+}$ such that $\alpha(w)=\beta(w)$. The standard undecidability
proof [28] constructs, given a Turing machine $M$, morphisms $\alpha,\beta$
such that for $w\in\Sigma^{*}$, any common prefix of $\alpha(w)$ and
$\beta(w)$ encodes a prefix of a computation history of $M$. For our decidable
set $D$, there exists a fixed terminating Turing machine, so we can proceed as
follows. Given a word $u\in D$, we can apply this construction to compute in
polynomial time morphisms $\alpha,\beta\colon\Sigma^{*}\to\\{1,2\\}^{*}$ such
that

  1. (i)

$u\in D$ iff there is a $w\in\Sigma^{+}$ with $\alpha(w)=\beta(w)$ and

  2. (ii)

there exists $k\in\mathbb{N}$ so that for every $w\in\Sigma^{*}$, the words
$\alpha(w)$ and $\beta(w)$ have no common prefix longer than $k$.

We claim that $u\in D$ if and only if $L_{\alpha,\beta}$ and $E$ are separable
by $\mathcal{B}\Sigma_{1}[\mathord{<},\mathsf{mod}]$. Clearly, if $u\in D$,
then the languages $L_{\alpha,\beta}$ and $E$ intersect and cannot be
separable. Suppose $u\notin D$. Then (ii) implies that $L_{\alpha,\beta}$ is
included in

$S_{k}=\\{a^{r}cb^{s}\mid r\not\equiv s\bmod 2^{k+1}\\}\\\
\cup\\{a^{r}cb^{s}\mid\min(r,s)<2^{k+1}-1,r\neq s\\}$

because $x,y\in\\{1,2\\}^{*}$, $|x|,|y|>k$, have a common prefix of length
$>k$ iff $\nu(x)\equiv\nu(y)\bmod{2^{k+1}}$. Moreover, for
$x\in\\{1,2\\}^{*}$, we have $|x|\leq k$ iff $\nu(x)<2^{k+1}-1$. Since $S_{k}$
is clearly definable in $\mathcal{B}\Sigma_{1}[\mathord{<},\mathsf{mod}]$ and
disjoint from $E$, this shows that $L_{\alpha,\beta}$ and $E$ are separable by
$\mathcal{B}\Sigma_{1}[\mathord{<},\mathsf{mod}]$. ∎