# Diameter Minimization by Shortcutting with Degree Constraints ††thanks: Both
authors are supported by the ERC Advanced Grant REBOUND (834862), the EC H2020
RIA project SoBigData (871042), and the Wallenberg AI, Autonomous Systems and
Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation

1st Florian Adriaens  KTH Royal Institute of Technology
Stockholm, Sweden
<EMAIL_ADDRESS>2nd Aristides Gionis  KTH Royal Institute of Technology
Stockholm, Sweden
<EMAIL_ADDRESS>
###### Abstract

We consider the problem of adding a fixed number of new edges to an undirected
graph in order to minimize the diameter of the augmented graph, and under the
constraint that the number of edges added for each vertex is bounded by an
integer. The problem is motivated by network-design applications, where we
want to minimize the worst case communication in the network without
excessively increasing the degree of any single vertex, so as to avoid
additional overload. We present three algorithms for this task, each with
their own merits. The special case of a matching augmentation –when every
vertex can be incident to at most one new edge– is of particular interest, for
which we show an inapproximability result, and provide bounds on the smallest
achievable diameter when these edges are added to a path. Finally, we
empirically evaluate and compare our algorithms on several real-life networks
of varying types.

###### Index Terms:

approximation algorithms, network design, edge augmentation, diameter
reduction.

##  I Introduction

The diameter of a graph is defined as the greatest distance between any pair
of vertices. It is a fundamental notion of a network, measuring the worst-case
point-to-point distance in information networks, social networks, and
communication networks. Ensuring a small diameter is a crucial property in
network-design applications, e.g., minimizing latency in multicore processor
networks [1], or forming a small-world network to maximize the influence of a
campaign [2].

There has been a considerable amount of research on the problem of augmenting
undirected graphs with new edges in order to minimize the diameter of the
resulting graph. This operation has been described in the literature as
_shortcutting_ [3, 4, 5, 6]; and the newly-added edges are referred to as
_shortcut edges_. Li, McCormick and Simchi-Levi [7] introduced the _Bounded
Cardinality Minimum Diameter_ (BCMD) problem, where the goal is to add at most
$k$ shortcut edges so as to minimize the diameter of the augmented graph.

(a) HIV network. (b) degree budget $\delta=3$. (c) degree budget $\delta=1$.

Figure 1: The result of our algorithm (Section IV-B) after adding $k=3$
shortcut edges (indicated by the red edges) to the HIV network [8, 9]. Fig.
(a) shows the original network. In (b) we have shortcut the network with a
degree increase constraint of $\delta=3$ for each vertex. In (c) we set
$\delta=1$, so the augmentation has to form a matching. The diameter of the
original network is 10, as indicated by a longest shortest path (blue dashed
edges). In both (b) and (c), the diameter of the augmented network is reduced
to 8.

A potential downside of the BCMD problem formulation is that optimal solutions
(and their approximations) might increase the degree of a single vertex by a
substantial amount. In fact, this is a guaranteed side effect for solutions
obtained by the known approximation algorithms for BCMD (see Section II), as a
common theme in many of these algorithms is that they first partition the
graph into $k+1$ non-overlapping parts (the clustering step), and then connect
the clusters by picking one cluster center and connecting it to the centers of
all other clusters. The latter step is called the _star-shortcutting_ step and
adds at most $k$ shortcut edges to the graph, by increasing the degree of a
single vertex by $k$. For certain applications, however, it is desirable to
limit the increase of the degree of any single vertex. Due to physical,
economical, or other limitations, many real-life network problems introduce
such a degree constraint [10, 5]. For example, the work of Bokhari and Raza
[11] was motivated by a question on how to decrease the diameter of a computer
network, by adding additional links, under the constraint that no more than
one I/O port is added to each processor. A second example is in the area of
social networks: a service provider might be interested in recommending new
friendships to users with the aim of increasing the overall connectivity of
the network, so as to facilitate information diffusion and reducing
polarization [12, 13, 14]. In [14] the largest distance between two members of
different groups (i.e., the _colored_ diameter) has been used a measure of
polarization. Recommending too many friendships to one individual user might
not result in many actual links being materialized, due to the risk of
overburdening that user. A better strategy might be to limit the number of
recommendations per individual user.

Motivated by these application scenarios and the need for a different
algorithmic approach than prior algorithms for BCMD, as _star-shortcutting_ is
not allowed anymore, we introduce and study a degree-constrained
generalization of BCMD (see Problem 1). In this variant, denoted as
BCMD-$\delta$, the increase of the degree of each vertex is limited to at most
$\delta$. The original BCMD problem corresponds to BCMD-$\delta$ with
$\delta=k$. Studying the BCMD problem with degree constraints was left as an
open question in the recent work of Tan, E. J. Van Leeuwen and J. Van Leeuwen.
[5]. Fig. 1 shows an illustrative example of the BCMD-$\delta$ problem, for
different settings of $\delta$. In Fig. 1b we have an unlimited degree
increase budget, corresponding to the original BCMD problem. In Fig. 1c we
illustrate a solution to the BCMD-$\delta$ problem with $\delta=1$: the vertex
degrees are allowed to increase by at most one, meaning that the newly added
edges have to form a matching in the augmented graph.

Preliminaries. All graphs $G=(V,E)$ in this paper are simple, undirected and
unweighted. Let $n=|V|$, and $m=|E|$. The distance $d_{G}(u,v)$ between two
vertices $u,v\in V$ is defined as the number of edges in a shortest path
between $u$ and $v$ ($\infty$ if no connecting path exists). The eccentricity
$e_{G}(u)=\max_{v\in V}d_{G}(u,v)$ of a vertex $u$ is the largest distance
between $u$ and any other vertex. The diameter $D_{G}=\max_{u,v\in
V}d_{G}(u,v)$ is the maximum eccentricity of any vertex. This distance between
two sets of vertices is always defined as the shortest distance between any
two vertices, one from each set. For $X\subseteq V$, the induced subgraph
$G[X]$ of $G$ by $X$ is the graph whose vertex set is $X$, and whose edge set
consists of all of the edges in $E$ that have both endpoints in $X$. In case
we omit the subscript in a notation, we always refer to the original graph
$G$.

Results and outline. Problem 1 introduces a generalization of the BCMD problem
that restricts the maximum degree increase of each vertex. Specifically, given
a budget $\delta$ for each vertex, we ask to augment the graph by adding at
most $k$ new edges so as to minimize the diameter of the augmented graph, and
the degree of each vertex increases by at most $\delta$.

######  Problem 1 (Bounded Cardinality Minimum Diameter with degree
constraints (BCMD-$\delta$)).

Given a graph $G=(V,E)$ and integers $k,\delta\geq 1$, find a set $M$ of at
most $k$ non-edges in $G$ that minimize the diameter of the augmented graph
$G^{\prime}=(V,E\cup M)$, and for all $v\in V$ it holds that
$\text{degree}_{G^{\prime}}(v)\leq\text{degree}_{G}(v)+\delta$.

In the most restrictive setting, which corresponds to $\delta=1$, each vertex
can be incident to at most one shortcut edge, so the augmentation has to form
a matching. Since this problem is of particular interest, we denote it as
BCMD-M (Bounded Cardinality Minimum Diameter with Matching constraint).

Our results are summarized as follows:

  1. 1.

In Section III we present lower and upper bounds on the optimum value of the
BCMD-M problem when the input graph is an $n$-vertex path, thereby extending a
result of Chung and Garey [10] to the setting of a matching augmentation.

  2. 2.

We give three algorithms for the BCMD-$\delta$ problem in Section IV. Section
IV-A details a $\mathcal{O}(\log_{\delta+1}k)$-approximation algorithm for
connected graphs. In Section IV-B we give a constant-factor approximation in
the case that $k\leq\sqrt{\delta n}-1$. Section IV-C details an intuitive
heuristic without guarantees. All algorithms need $\mathcal{O}(km)$ time, and
hence scale quite well for limited values of $k$.

  3. 3.

In Section VI we show that there exists no
$(\frac{4}{3}-\epsilon)$-approximation for BCMD-M, assuming
$\mathbf{P}\neq\mathbf{NP}$.

  4. 4.

In Section VII we empirically evaluate and compare the performance of our
algorithms proposed in Section IV on real-life networks of varying types and
sizes.

##  II Related work

Several constant-factor approximation algorithms for the BCMD problem, and
weighted variants thereof, are known. Besides proving
$\mathbf{NP}$-completeness, Li, McCormick and Simchi-Levi [7] proposed an
elegant $(4+\frac{2}{D^{*}})$-approximation algorithm for BCMD, where $D^{*}$
denotes the smallest achievable diameter. Bilò, Gualà and Proietti [15]
refined the performance analysis of [7], and showed that the algorithm in fact
guarantees a $(2+\frac{2}{D^{*}})$-approximation. Demaine and Zadimoghaddam
[3] considered weighted graphs, with the requirement that all shortcut edges
have an equal nonnegative weight, and they provided a
$(4+\epsilon)$-approximation for arbitrary $\epsilon>0$. Dodis and Khanna [16]
generalized the problem by assigning costs to the shortcut edges, and
requiring that the sum of the costs of all shortcut edges does not exceed a
given budget parameter. They showed that the general variant of BCMD, with
arbitrary positive edge weights and arbitrary nonnegative shortcut edge costs,
admits a $(2+\frac{2}{D^{*}})$-approximation if one is allowed to exceed the
budget by a factor of $\mathcal{O}(\log k)$. Finally, Frati et al. [17] showed
that the general variant of BCMD admits a fixed-parameter tractable
4-approximation algorithm.

Prior work on shortcutting with degree constraints. The problem of
shortcutting a graph while respecting degree constraints has been studied
before. Chung and Garey [10] provided lower and upper bounds on the smallest
achievable diameter when edges are added to a path. They posed it as an open
question to extend their results when there is a constraint on the maximum
degree increase of each vertex. In Section III we extend their bounds to the
case of a matching augmentation ($\delta=1$). Bollobás and Chung [18] showed
that adding a random matching of maximum possible size to a cycle gives a
graph with diameter close to the optimum value, which is about $\log_{2}n$.
Bokhari and Raza [11] proved that by adding at most
$\left\lfloor\frac{n}{2}\right\rfloor$ matching edges, any connected graph can
be shortcut to a diameter of $\mathcal{O}(\log n)$. More recently, Tan et al.
[5] improved the results of [11] and showed that $\mathcal{O}(\frac{n}{\log
n})$ matching edges are sufficient to achieve a diameter of $\mathcal{O}(\log
n)$. Moreover, they provided several complexity results on the dual problem
(see also [17, 19]), i.e., minimizing the number of edges that need to be
added to achieve a target diameter, while respecting degree constraints.

##  III Warm up: Shortcutting a path with matching edges

We present several results on the BCMD-M problem when the input graph is an
$n$-vertex path. The ideas presented here are intuitive and they serve as a
building block for our shortcutting algorithms on general graphs in Section
IV.

Chung and Garey [10] provided lower and upper bounds on the smallest
achievable diameter when $k$ shortcut edges are added to an $n$-vertex path,
without any constraints on the maximum increase of the degrees. They proved
that it is not possible to achieve a diameter smaller than $\frac{n}{k+1}-1$,
and gave an algorithm that reduces the diameter to $\frac{n}{k+1}+3$. In the
following sections we extend their bounds on the smallest achievable diameter
when the vertex-degree increase is limited to one, i.e., when $k$ matching
edges are added to a path.

###  III-A Lower bound

Let $M(n,k)$ denote the smallest achievable diameter after adding $k$ matching
edges to an $n$-vertex path. The lower bound of Chung and Garey [10] also
applies to our setting, and we immediately find that
$M(n,k)\geq\frac{n}{k+1}-1$. On the other hand, it is known that any graph
with maximum degree three has diameter at least $\log_{2}(n)-2$ [18]. Theorem
1 unifies both results into one lower bound. Theorem 2 gives a method that
achieves this lower bound, up to constant factors.

######  Theorem 1.

For all $1\leq k\leq n/2$, the smallest achievable diameter after adding $k$
matching edges to an $n$-vertex path satisfies

$\displaystyle M(n,k)\geq\frac{n}{2(k+1)}+\log_{2}(k+1)-2.$ (1)

###### Proof:

Consider the rooted shortest-path tree $T$ formed by a breadth-first-search
(BFS) in the optimal augmentation (i.e., a shortcutting that achieves diameter
$M(n,k)$), starting from a vertex $v$, until we encounter all vertices. The
height $h_{T}$ of $T$ is a lower bound for $M(n,k)$. We provide a lower bound
to $h_{T}$ to establish the result. The height $h_{T}$ is minimized when the
degree-three vertices are explored first, since the degree-two vertices do not
lead to any branching in $T$. So we may assume that the first levels of $T$
are filled with degree-three vertices (in particular, the root vertex $v$ has
degree three), after that the degree-two and vertices, and finally the degree-
one vertices. Furthermore, we may assume that none of the added $k$ shortcut
edges are incident to any of the two endpoints of the path. Since in this
case, we have the maximum possible number of degree-three vertices, which
yields the smallest possible height $h_{T}$. After the addition of any such
set of $k$ matching edges, there are $2k$ vertices of degree three, $n-2k-2$
vertices of degree two, and the two endpoints of the path have degree one.

Let level $i$ be the largest level containing degree-three vertices, where we
place the root vertex $v$ at level 0. There are $2k$ degree-three vertices, so
it follows that
$i=\left\lceil{\log_{2}(\frac{2k+2}{3})}\right\rceil\geq\log_{2}(k+1)-1$.
After encountering the degree-three vertices in $T$, we encounter the degree-
two vertices and ultimately the two degree-one endpoints of the path. Some of
the degree-two vertices might be at level $i$, but from level $i+1$ the tree
consists only of vertices with degree at most two. This implies that the tree
$T$ will not branch any further after level $i+1$. We now quantify how many
additional levels the remaining $n-2k$ vertices of degree at most two induce.
Note that there are at most $k+1$ degree-three vertices at level $i$, and this
is tight if the level $i$ is filled fully with degree-three vertices. It
follows that the additional number of levels induced by the $n-2k$ remaining
vertices of at most degree-two is at least $\frac{n-2k}{2(k+1)}$, since the
degree-three vertices at level $i$ might induce two branches of degree-two
vertices in level $i+1$. Hence,

$\displaystyle M(n,k)\geq h_{T}$
$\displaystyle\geq\frac{n-2k}{2(k+1)}+\log_{2}(k+1)-1$
$\displaystyle\geq\frac{n}{2(k+1)}+\log_{2}(k+1)-2.$

∎

###  III-B Upper bound

Next we describe a procedure that achieves a matching upper bound, up to
constant factors.

######  Definition 1.

A full (or Moore) d-tree is an (undirected) rooted tree in which every vertex
has degree $d$, and all levels are filled to maximum size except possibly the
leaf level [5, Section 2.1.2].

######  Theorem 2.

For all $1\leq k\leq n/2$, the smallest achievable diameter after adding $k$
matching edges to an $n$-vertex path satisfies

$\displaystyle M(n,k)\leq\frac{n}{k+1}+4\log_{2}(k+1)+1.$ (2)

###### Proof:

First, we discuss a procedure when $k\leq\frac{n}{3}-1$. We divide the path
into $k+1$ non-overlapping intervals of roughly equal size. For every interval
we find the center vertex, i.e., the midpoint of the interval. If there is a
tie between two centers, choose one arbitrarily. Each interval will contain at
least $\left\lfloor{n/(k+1)}\right\rfloor$ vertices and at most
$\left\lceil{n/(k+1)}\right\rceil$ vertices. The distance from any vertex to
the center of its respective interval is at most
$\left\lceil{n/(k+1)}\right\rceil/2$. Since $k\leq\frac{n}{3}-1$, every
interval has at least three vertices. In each interval we select a line
_segment_ (a path of length two) consisting of the left-neighbor of the
center, the center itself, and the right-neighbor of the center (see Fig. 2a).
We now connect the segments by embedding them into a _full 3-tree_ (see
Definition 1). The segments are regarded as supernodes in the tree. Take an
arbitrary segment as the root in the tree, and shortcut each vertex in the
segment to the centers of three other segments. Each of these three segments
will now be shortcut to the centers of two new segments and so on, until all
segments are part of the tree. Note that all vertices are incident to at most
one shortcut edge. Fig. 2b) gives an example of how such a construction looks
like.

(a)

(b)

Figure 2: a) Dividing the path into $k+1$ intervals $I_{i}$. A segment
consists of an interval center (red) together with its two neighbors (pastel
red). b) Embedding the segments into a full 3-tree. Dashed edges indicate the
newly added edges.

The height of this tree is at most $\log_{2}(k+1)$, and it takes at most two
steps to traverse each segment. So the distance between any two center
vertices in the shortcutted graph is at most $4\log_{2}(k+1)$. The distance
from an arbitrary vertex to the closest segment in the same interval is at
most $\left\lceil{n/(k+1)}\right\rceil/2$. The total diameter D of the
shortcutted graph is hence bounded by

$\displaystyle
D\leq\left\lceil\frac{n}{k+1}\right\rceil+4\log_{2}(k+1)\leq{\frac{n}{k+1}}+4\log_{2}(k+1)+1.$

In case that $k>\frac{n}{3}-1$, it suffices to add $\frac{n}{3}-1$ edges in
the aforementioned manner. Indeed, a straightforward calculation shows that
the bound (2) is increasing as a function of $k$, when
$k>\frac{n\ln(2)}{4}-1$. ∎

Figure 3: A graph with diameter $n/2-1$ that is shortcut to a graph with
diameter four by adding $k=n/2-1$ matching shortcut edges (dashed edges).

###  III-C Achievable diameter in connected graphs

Chung and Garey [10, Section 3] used their lower bound on the achievable
diameter of a shortcutted path to show that any connected graph with diameter
$D$ cannot be shortcut to a diameter less than $\frac{D+1}{k+1}-1$, using at
most $k$ edges. One can try to extend their result to our case of matching
shortcut edges, but the example in Fig. 3 shows that their bound is tight in
certain cases. The example shows a graph with diameter $n/2-1$ (assume that
$n$ is even) that is being shortcut to a graph with diameter four by adding
$k=n/2-1$ matching edges. This is in contrast with shortcutting a path, which
also has diameter linear in $n$. However, unlike the example in Fig. 3, a path
has constant vertex degrees and this restricts the achievable diameter.
Indeed, Theorem 1 states that adding any $k=n/2-1$ matching edges to an
$n$-vertex path gives a graph with diameter at least $\log_{2}(n)-2$. For
shortcutting general connected graphs with diameter $D$ with matching edges,
it appears one cannot improve the lower bound of $\mathcal{O}(\frac{D}{k})$ as
given by [10] without taking into account additional information about the
graph (e.g., degrees).

##  IV Shortcutting general graphs

We present three algorithms for shortcutting general graphs with degree
constraints. In Section IV-A we present an algorithm that achieves a
$\mathcal{O}(\log_{\delta+1}k)$-approximation for connected graphs. In Section
IV-B we present a constant-factor approximation when $k\leq\sqrt{\delta n}-1$.
In Section IV-C we detail a fast heuristic without approximation guarantees.
All three algorithms need $\mathcal{O}(km)$ time, making them scalable on most
real-life networks when $k$ is not too large.

###  IV-A A $\mathcal{O}(\log_{\delta+1}k)$-approximation for connected
graphs.

The high-level strategy is reminiscent of the path case. After finding at most
$k+1$ small connected segments in the graph, we embed them into a full tree by
connecting the segments using at most $k$ shortcut edges. The branching factor
of the tree will depend on the degree budget $\delta$ and the size of the
segments. The main difference with the path case is that we will require the
segments to be far apart (this will later be defined more precisely). Our
strategy consists of first finding a maximal family of vertex-disjoint
segments. From this family, we select a set of at most $k+1$ segments that are
far apart, using a similar idea as the $k$-center heuristic of Dyer and Frieze
[20, 21]. This heuristic has been used in previous algorithms for the BCMD
problem [15, 17, 7], and allows us to bound the maximum distance, in terms of
the optimum diameter, of a vertex to the chosen set of $k+1$ segments
(Corollary 1).

We start by formally defining a segment.

######  Definition 2.

A $\beta$-_segment_ $C$, for $1\leq\beta\leq n$, is a set of vertices
$C\subseteq V$ with $|C|=\beta$, such that the induced subgraph $G[C]$ is
connected.

The following proposition bounds the distance between a vertex and a maximal
family of vertex-disjoint segments.

######  Proposition 1.

Assume $G$ is connected. For any _maximal_ family
$\mathcal{C}=\\{C_{1},\ldots,C_{\alpha}\\}$ of vertex-disjoint
$\beta$-segments, it holds that $\forall v\notin\cup_{i=1}^{\alpha}C_{i}$:
$d_{G}(v,\mathcal{C})\leq\beta-1$.

###### Proof:

Suppose for some $v\notin\cup_{i=1}^{\alpha}C_{i}$ we have
$d_{G}(v,\mathcal{C})>\beta-1$. Since $G$ is connected, there is a shortest
path from $v$ to $\cup_{i=1}^{\alpha}C_{i}$ that consists of at least $\beta$
vertices that are not in $\cup_{i=1}^{\alpha}C_{i}$, contradicting the
maximality of $\mathcal{C}$. ∎

Algorithm 1 Log. approximation BCMD-$\delta$.

1:graph $G$, $k\geq 1$, $\delta\geq 1$ and $3\leq\beta\leq n$.

2:$\mathcal{X}\leftarrow\emptyset$

3:$\mathcal{C}$ = a maximal family of disjoint $\beta$-segments.

4:for $\min\\{k+1,|\mathcal{C}|\\}$ times do

5: Pick segment $C^{*}\in\mathcal{C}\setminus\mathcal{X}$ with
$d_{G}(C^{*},\mathcal{X})=\max_{C\in\mathcal{C}\setminus\mathcal{X}}d_{G}(C,\mathcal{X})$.

6: $\mathcal{X}\leftarrow\mathcal{X}\cup\\{C^{*}\\}$.

7:end for

8:Connect the segments in $\mathcal{X}$ into a full $d$-tree with
$d=\beta\,\delta$, such that every vertex has at most $\delta$ incident
shortcut edges. See Fig. 2b for an example with $\delta=1$ and $\beta=3$.

Let $D_{k}^{*}$ denote the minimum achievable diameter after adding at most
$k$ edges to $G$ (the optimum of BCMD), and let $D^{*}_{k,\delta}$ be the
minimum achievable diameter after adding at most $k$ edges to $G$, without
increasing the degree of any vertex by more than $\delta\geq 1$ (the optimum
of BCMD-$\delta$).

After running Algorithm 1 (lines 1–6), we prove (Lemma 1) that the distance
from any remaining segments in $\mathcal{C}\setminus\mathcal{X}$ to
$\mathcal{X}$ is bounded by $D^{*}_{k,\delta}$. The first segment in
$\mathcal{X}$ can be chosen arbitrarily. Algorithm 1 (lines 3–6) then selects
segments with the largest distance from the already selected ones.

######  Lemma 1.

For all $\beta$-segments $C\in\mathcal{C}\setminus\mathcal{X}$ it holds
$d_{G}(C,\mathcal{X})\leq D^{*}_{k,\delta}$.

###### Proof:

We can assume that $\mathcal{C}\setminus\mathcal{X}\neq\emptyset$. This
implies that $k+1<|\mathcal{C}|$, and thus $|\mathcal{X}|=k+1$. Suppose there
exists a $\beta$-segment $C\in\mathcal{C}\setminus\mathcal{X}$ such that
$d_{G}(C,\mathcal{X})>D^{*}_{k}$. Algorithm 1 greedily selects the segments
that are furthest away from the already selected set of segments, This implies
that when the iteration (lines 3–6) terminates we have a set of
$|\mathcal{X}|+1=k+2$ segments with pairwise distances between them that is
larger than $D^{*}_{k}$. In particular, we have a set of at least $k+2$
vertices with pairwise distances larger than $D^{*}_{k}$. Now we use the
following proposition — the proof can be found in the paper of Frati et al.
[17, Claim 1]:

######  Proposition 2.

[17, Claim 1] Let $X\subseteq V$ be a set of vertices with $|X|\geq 3$ and
$d(u,v)>\alpha$, for all $u\neq v\in X$, for some $\alpha>0$. Then for any
graph $G^{\prime}=G\cup\\{e\\}$, where $e\in{V\choose 2}$, there exists a
subset $X^{\prime}\subseteq X$ with $|X^{\prime}|=X-1$, such that
$d_{G^{\prime}}(u,v)>\alpha$, for all $u\neq v\in X^{\prime}$.

By iteratively applying Proposition 2, any graph $G^{\prime}$ obtained by
adding any $k$ shortcut edges (not necessarily with degree-constraints) to $G$
will have a set of at least two vertices with pairwise distances in
$G^{\prime}$ strictly larger than $D^{*}_{k}$, which contradicts the
optimality of $D^{*}_{k}$. So it must be that $\forall
C\in\mathcal{C}\setminus\mathcal{X}$ it holds that $d_{G}(C,\mathcal{X})\leq
D^{*}_{k}$, and the result follows since $D_{k}^{*}\leq D^{*}_{k,\delta}$. ∎

Lemma 1 enables us to bound the distance from any vertex $v$ to the set of
segments $\mathcal{X}$, as given by the following corollary.

######  Corollary 1.

Assume $G$ is connected. For all vertices $v\in V$ it holds
$d_{G}(v,\mathcal{X})\leq\beta-1+D^{*}_{k,\delta}$.

###### Proof:

If $|\mathcal{C}|\leq k+1$, then $d_{G}(v,\mathcal{X})\leq\beta-1$ since
$\mathcal{X}=\mathcal{C}$ after running Algorithm 1 (lines 1–6) and because
$\mathcal{C}$ is a maximal family of $\beta$-segments (Proposition 1). If
$|\mathcal{C}|>k+1$, then $\mathcal{C}\setminus\mathcal{X}\neq\emptyset$ and
the result follows from Lemma 1 and the triangle inequality. ∎

Now we are ready to analyse Algorithm 1:

######  Theorem 3.

Assume $G$ is connected. Algorithm 1 returns a shortcutted graph whose
diameter is at most
$2(\beta-1+D^{*}_{k,\delta}+\beta\log_{\beta\delta-1}(k+1))$, by adding at
most $k$ edges to $G$.

###### Proof:

By Corollary 1, the distance in $G$ (and thus, also in the augmented graph) of
any vertex to its nearest segment in $\mathcal{X}$ is at most
$\beta-1+D^{*}_{k,\delta}$. The constructed full $d$-tree has height at most
$\log_{\beta\delta-1}$ (since $\beta\geq 3$ and $\delta\geq 1$, otherwise
there is no branching of the tree), and it takes at most $\beta-1$ steps to
traverse each $\beta$-segment. Hence, the total distance in the augmented
graph between any two segments in $\mathcal{X}$ is at most
$2\beta\log_{\beta\delta-1}|\mathcal{X}|$. So the total diameter is at most
$2(\beta-1+D^{*}_{k,\delta}+\beta\log_{\beta\delta-1}|\mathcal{X}|)$. The
result follows since $|\mathcal{X}|\leq k+1$.

Note that Algorithm 1 (line 7) adds at most $k$ shortcut edges to the original
graph; constructing the full $d$-tree needs at most $|\mathcal{X}|-1$ edges,
and $|\mathcal{X}|\leq k+1$ (line 3). ∎

######  Corollary 2.

Assume $G$ is connected. Algorithm 1 is a
$\mathcal{O}(\log_{\delta+1}k)$-approximation for the BCMD-$\delta$ problem,
for the choice $\beta=3$.

###### Proof:

If $D^{*}_{k,\delta}\geq\log_{3\delta-1}(k+1)$, then Theorem 3 gives a
constant-factor guarantee. If $D^{*}_{k,\delta}<\log_{3\delta-1}(k+1)$ then
the resulting diameter guarantee is $\mathcal{O}(\log_{\delta+1}k)$, and the
result follows since $D^{*}_{k,\delta}\geq 1$. ∎

Running time. Algorithm 1 needs $\mathcal{O}(km)$ time for connected graphs
when $\beta=3$. Finding a maximal family of 3-segments (line 2) can be done in
linear time $\mathcal{O}(m)$ (see e.g., [5, Section 3.1]). Lines 3–5 can be
implemented in $\mathcal{O}(km)$ time (similarly as in the k-center heuristic
[20]); in every iteration, keep a dictionary of the distances from all
segments to the current set $\mathcal{X}$. After adding $C^{*}$ to
$\mathcal{X}$, we update the dictionary efficiently by first computing the
distances from $C^{*}$ to all other segments (by doing a BFS in
$\mathcal{O}(m)$ time), and then for each segment taking the minimum of the
old dictionary value and this newly computed distance.

###  IV-B Constant-factor approximation for small $k$

Algorithm 2 Constant approximation BCMD-$\delta$.

1:graph $G$, $1\leq k\leq\sqrt{\delta n}-1$, $\delta\geq 1$.

2:$\\{c_{i}\\}=k+1\text{ cluster centers computed according to
\cite[cite]{[\@@bibref{}{DYER1985285}{}{}]}}.$

3:$C_{\max}\text{ }(c_{\max})\leftarrow\text{ largest cluster (center)}$.

4:$\forall c_{i}\neq c_{\max}$:  add edge  $(c_{i},v)$ for some $v\in
C_{\max}$ s.t. $v$ is incident to less than $\delta$ new shortcut edges.

In case when $k\leq\sqrt{\delta n}-1$, we obtain a constant-factor
approximation for the BCMD-$\delta$ problem, even for disconnected graphs,
using a slightly different approach. Algorithm 2 first computes $k+1$ non-
necessarily distinct cluster centers (line 1), again according to the
$k$-center heuristic of Dyer and Frieze [20, 21]. In particular, the
clustering phase (line 1) computes a set of $k+1$ non-necessarily distinct
cluster centers $C=\\{c_{1},\ldots,c_{k+1}\\}\subseteq V$ as follows: the
first center $c_{1}$ is an arbitrary vertex. For $2\leq i\leq k+1$, the center
$c_{i}$ is chosen as a vertex that maximizes the distance
$d_{G}(c_{i},\\{c_{1},\ldots,c_{i-1}\\})$. The cluster partitions are defined
by assigning every non-center vertex to the nearest center, breaking ties
arbitrarily. If $k$ is small (or $\delta$ is large), we can prove that the
largest cluster contains enough vertices to shortcut to all other centers,
leading to a constant-factor approximation. Fig. 4 shows an example in case of
$\delta=1$. Lemma 2 formalizes this.

######  Lemma 2.

If $k\leq\sqrt{\delta n}-1$, Algorithm 2 is a
$(4+2/D^{*}_{k,\delta})$-approximation algorithm for BCMD-$\delta$.

###### Proof:

The average number of vertices per cluster is $\frac{n}{k+1}$. So the largest
cluster has the capacity to shortcut to at least $\delta\frac{n}{k+1}\geq k$
other vertices. Thus, Algorithm 2 (line 3) shortcuts every center from the $k$
other clusters to an arbitrary vertex in the largest cluster, while respecting
the degree constraints of all the vertices in the largest cluster. In previous
work [15, 17] it was proven that the heuristic [20] computes a set of centers
$C$ such that for all $v\in V$ it holds $d_{G}(v,C)\leq D_{k}^{*}$. Since
$D_{k}^{*}\leq D^{*}_{k,\delta}$, it holds that the radius of each cluster is
also upper bounded by $D^{*}_{k,\delta}$. So the distance to travel the
largest cluster is at most $2D^{*}_{k,\delta}$, and the diameter of the
shortcutted graph is at most $4D^{*}_{k,\delta}+2$. ∎

Figure 4: Schematic idea of the constant-factor approximation. In this
example, we consider a matching augmentation ($\delta=1$). The radius of each
cluster is upper bounded by the optimum diameter $D^{*}_{k,\delta}$, and the
largest cluster has enough vertices to shortcut (dashed red edges) to the
centers (green) of the other clusters.

Running time. The running time of Algorithm 2 is $\mathcal{O}(km)$, since the
bottleneck is the $k$-center heuristic from [20].

Extending to larger depths. We can strengthen the idea behind Algorithm 2, by
relaxing the requirement that the largest cluster needs to connect to all the
other clusters. Instead, one can allow more than one level of the tree. For
simplicity, we discuss the case of a matching augmentation ($\delta=1$). We
discuss how to build a tree when $k=\mathcal{O}(n^{1-\epsilon})$, for some
$0<\epsilon<1/2$. First run the clustering heuristic (line 1), and then sort
the clusters by cluster size (number of vertices). The largest cluster is the
root of the tree, and is connected to the second largest cluster, third
largest cluster etc., until all vertices in the largest cluster have been
shortcut. Then we repeat the process with the second largest cluster, and
connect its vertices to the remaining largest clusters, placing these clusters
one level below. One might wonder if it is always possible to connect all the
clusters into one tree. For example, if all the clusters are singleton
vertices, then this is not possible. Or if we have one cluster of four
vertices, and five remaining singleton clusters then this is also not
possible.

However, such cases are always avoided. To see this, we use the fact that any
nonnegative integer sequence $d_{1},\ldots,d_{k+1}\geq 1$ is the degree
sequence of a tree with $k$ edges if and only if $\sum d_{i}=2k$. In our case,
every cluster $C_{i}$ can be seen as a supernode with a maximum degree
capacity that is equal to the cluster size $|C_{i}|$ (every vertex in a
cluster can be incident to at most one shortcut edge). Since
$\sum|C_{i}|=n\geq 2k$, there is in fact always a tree with at most $k$ edges
that connects the $k+1$ clusters. It is also not hard to see that our specific
approach (largest clusters first) always works.

The height of this tree will be largest when all the clusters have the same
size $\frac{n}{k+1}$, i.e, when branching uniformly. Assuming
$\frac{n}{k+1}\geq 3$, the diameter of the shortcutted graph is at most

$\displaystyle(4D^{M}_{k}+2)\log_{\frac{n}{k+1}-1}(k+1),$

since it takes at most $2D^{M}_{k}$ steps to transverse each cluster. If
$k=\mathcal{O}(n^{1-\epsilon})$ with $0<\epsilon<1/2$, then for $n$ large
enough we have $\frac{n}{k+1}\geq 3$, so the diameter is at most
$(4D^{M}_{k}+2)\mathcal{O}(\frac{1}{\epsilon})$.

###  IV-C Greedy 2-Sweep heuristic

Lastly, we propose a third intuitive heuristic that works well in practice,
but comes without any approximation guarantees. It is inspired by the fast
heuristic lower bound called 2-Sweep [22], that is used to estimate the
diameter in large graphs. Algorithm 3 picks a vertex $u$ that is furthest away
from a randomly chosen vertex, such that $u$ has less than $\delta$ shortcut
edges incident to it. Then it picks a vertex $v$ that is furthest away from
$u$, also incident to less than $\delta$ shortcut edges. Add the shortcut edge
$\\{u,v\\}$. Repeat $k$ times. The Greedy 2-Sweep heuristic attempts to
shortcut the two furthest vertices in the graph, with respecting budget
constraints. Since determining the two furthest vertices is not feasible for
large graphs, this heuristic approximately tries to find the two furthest
vertices. Running time of this heuristic is $\mathcal{O}(km)$, similar to the
previous algorithms.

Algorithm 3 Greedy 2-Sweep heuristic BCMD-$\delta$.

1:graph $G$, $k\geq 1$, $\delta\geq 1$.

2:$G^{\prime}\leftarrow G$

3:$\forall v\in V:\delta(v)=0$.

4:repeat $k$ times

5: pick uniform random $u\in\\{v\in V:\delta(v)<\delta\\}$.

6: $v\leftarrow\text{arg}\max_{\\{v\in
V:\delta(v)<\delta\\}}d_{G^{\prime}}(u,v)$

7: $G^{\prime}\leftarrow G^{\prime}\cup\\{u,v\\}$.

8: $\delta(v)\leftarrow\delta(v)+1$.

9: $\delta(u)\leftarrow\delta(u)+1$.

##  V Variants

We briefly discuss two variants of the BCMD-$\delta$ problem, and show that
any approximation algorithm for BCMD-$\delta$ can be used as an approximation
algorithm for these variants with a loss of a factor two.

Single-source. In the single-source variant of BCMD-$\delta$, we optimize the
eccentricity of a designated source vertex instead of the diameter of the
entire graph.

######  Lemma 3.

An $\alpha$-approximation for BCMD-$\delta$ is a $2\alpha$-approximation for
the single-source variant.

###### Proof:

The proof is similar to [3, Section 4]. ∎

Colored diameter. Suppose we have a disjoint partition of the vertices
$V=V_{1}\cup V_{2}$, where $V_{1},V_{2}\neq\emptyset$ and $V_{1}\cap
V_{2}=\emptyset$. Now define the _colored diameter_ as the longest shortest
path length between a vertex from $V_{1}$ and a vertex $V_{2}$. In several
scenarios, it might be the case that one only cares about minimizing the
colored diameter instead of the actual diameter. For example, [14] used the
colored diameter as a measure of polarization between two opposing groups. So
in this variant of the BCMD-$\delta$ problem we aim to minimize the colored
diameter, by shortcutting the graph without exceeding a degree budget for each
vertex. It is not hard to see that our algorithms can used for this task as
well:

######  Lemma 4.

An $\alpha$-approximation for BCMD-$\delta$ is a $2\alpha$-approximation for
the colored variant.

###### Proof:

Let $D^{*}$ (resp. $D_{\text{col}}^{*}$) be the optimum (resp. colored)
diameter of the graph after adding $k$ shortcut edges to the graph, while
respecting the degree constraints. Adding $k$ edges that minimize the diameter
to $D^{*}$ gives a graph with colored diameter at most $D^{*}$, so we have
$D_{\text{col}}^{*}\leq D^{*}$. On the other hand, adding $k$ edges that
minimize the colored diameter to $D_{\text{col}}^{*}$ gives a graph with
diameter at most $2D_{\text{col}}^{*}$ (triangle inequality). This implies
that $D^{*}\leq 2D_{\text{col}}^{*}$. So using an $\alpha$-approximation for
BCMD-$\delta$, we get a graph with diameter at most $\alpha D^{*}$. The
colored diameter of this augmented graph is also at most $\alpha D^{*}$, which
is at most $2\alpha D_{\text{col}}^{*}$. ∎

##  VI Inapproximability of BCMD-M

We start our analysis by reducing the $\mathbf{NP}$-complete SetCover problem
[23] to BCMD-M to show that we cannot get an approximation ratio better than
$4/3$. The reduction is reminiscent of a reduction proposed by Demaine and
Zadimoghaddam [3] to show an inapproximability result for the single-source
version of BCMD, but the analysis is more involved.

An instance of the SetCover problem consists of $p$ sets $S_{1},\ldots,S_{p}$
whose union consists of $l$ items. The goal is to find the minimum number of
sets whose union contains all $l$ items. We construct a graph $H$ as follows:
for every set $S_{i}$ we introduce a vertex $s_{i}$ and for every item $j$ we
introduce a vertex $u_{j}$. If an item $j$ is in a set $S_{i}$ we add an edge
from $u_{j}$ to $s_{i}$. All vertices $s_{i}$ are connected to each other
forming an $p$-clique. We add two more vertices $a$ and $b$. Vertex $a$ is
connected to all the set vertices $s_{i}$ and to $b$. Finally, we add another
clique of $k+1$ vertices $x_{1},\ldots,x_{k+1}$, and connect them to vertex
$b$. Fig. 5 shows a schematic example of this construction.

Figure 5: Construction of the graph $H$ used in the reduction from SetCover to
BCMD-M (Section VI).

The diameter of graph $H$ is equal to four. Indeed, the longest shortest paths
are between the vertices $u_{1},\ldots,u_{l}$ and the vertices
$x_{1},\ldots,x_{k+1}$, and these are the only shortest paths of length four.
The distance between two vertices $u_{i}$ and $u_{j}$ is at most three, since
we can assume that every item is part of some set and all the set vertices
$s_{1},\ldots,s_{p}$ form an $p$-clique. The task of the BCMD-M problem is now
to add $k$ matching shortcut edges to $H$ such that its diameter is minimized.
We first prove the following:

######  Proposition 3.

There exists a set of $k$ matching shortcut edges that reduce the diameter of
$H$ to at most three if and only if there exists a set-cover solution with
size at most $k$.

###### Proof:

If there exists a set-cover solution with size at most $k$, then we can add at
most $k$ matching edges between the vertices $x_{1},\ldots,x_{k}$ and the $k$
set vertices that correspond to the set-cover solution. The exact manner in
which they are connected does not matter, the resulting graph will have
diameter at most three. Indeed, between any two vertices $u_{i}$ and $x_{j}$,
there is an edge from $u_{i}$ to the chosen set which covers $u_{i}$, then
there is a shortcut edge to the $x$-clique, from where we need at most one
step to reach $x_{j}$.

Reversely, we show that if there exists a set of $k$ shortcut matching edges
that reduce the diameter to at most three, then there exists a set-cover
solution with size at most $k$. To see this, we prove the existence of a
solution that only uses shortcut edges between the $s$-vertices and the
$x$-vertices. We require that $n\geq 2$ and $l,p>k$. Consider a solution for
BCMD-M that reduces the diameter of $H$ to three and uses a different shortcut
edge $e$. We first examine the easy cases regarding $e$:

(ii) Edge $e$ is between some $x_{j}$ and $a$. Because of the matching
constraint, any shortest path from a $u$-vertex to $a$ still needs two steps.
Thus, the only purpose of this edge is to reduce the distance between $x_{j}$
and all the $u$-vertices to three, since any shortest path between
$x_{j^{\prime}}$ ($j^{\prime}\neq j$) and some $u_{i}$ that uses this edge
still has length four. We can replace this edge by an edge between $x_{j}$ and
any set vertex, the distance between $x_{j}$ and all the $u$-vertices is still
at most three.

(iii) Edge $e$ is between some $u_{i}$ and $a$. The only purpose of this edge
is to reduce the distance between $u_{i}$ and the $x$-vertices to three. One
can replace this edge with an edge between a set vertex that is connected to
$u_{i}$ and some $x_{j}$. The distance between $u_{i}$ and the $x$-vertices is
still at most three.

(iv) Edge $e$ is between some $u_{i}$ and $b$. The only purpose of this edge
is to reduce the distance between $u_{i}$ and all the $x_{j}$ to two. One can
replace this edge with an edge between a set vertex that is connected to
$u_{i}$ and some $x_{j}$. The distance between $u_{i}$ and the $x$-vertices is
still at most three.

(v) Edge $e$ is between some $s_{i}$ and $b$. The only purpose of this edge is
to reduce the distance between the item vertices connected to $s_{i}$ and all
the $x_{j}$ to three. One can replace this edge with an edge between $s_{i}$
and some $x_{j}$. The distance between all the item vertices connected to
$s_{i}$ and the $x$-vertices is still at most three.

(vi) Edge $e$ is between two $u$-vertices. The only possible purpose of this
edge would be to reduce the distance between one of the two $u$ vertices and
one specific $x_{i}$ vertex to three, since both endpoints of $e$ have already
been shortcut. Replacing this edge by an edge between a corresponding set
vertex and any $x$ vertex results in a graph where these shortest paths are
still at most three.

(vii) Edge $e$ is between some $u_{i}$ and $s_{j}$. The only purpose of this
edge would be to reduce the distance between $u_{i}$ and one specific $x_{k}$
to three (by shortcutting $a$), since $s_{j}$ has already been shortcut.
Replacing this edge by an edge between a $s_{j}$ and any $x$ vertex results in
a graph where these shortest paths are still at most three.

After rewiring edges according to the previous cases, we end up with a
solution where all of the shortcut edges are either between a $u$-vertex and
an $x$-vertex, or an $s$-vertex and an $x$-vertex. Suppose a vertex $u_{i}$
does not have a shortcut edge to any of the $x$-vertices. We can prove that
there must exist a set vertex that covers $u_{i}$ and is shortcut to one of
the $x$-vertices.

Suppose, by contradiction, that $u_{i}$ is not shortcut to the $x$-vertices,
and does not have a covering set vertex that is shortcut to the $x$-vertices.
There are two cases. First, consider the case when $u_{i}$ has a shortest path
that first visits another $u_{j}$ vertex, and then a shortcut edge from
$u_{j}$ to one of the $x$-vertices. This would take at least three steps,
since it takes at least two steps to move from $u_{i}$ to $u_{j}$. Moreover,
it would only reduce the distance from $u_{i}$ to one specific $x$-vertex to
three (since we need an extra step to reach the other $x$-vertices). Secondly,
suppose $u_{i}$ follows a shortest path that first visits a set vertex
containing $u_{i}$, and then to another set vertex (which does not contain
$u_{i}$) that is shortcut to the $x$-vertices. This also requires three steps,
and again it would only reduce the distance from $u_{i}$ to one specific
$x$-vertex to three. Since there are $k+1$ $x$-vertices, but only $k$ shortcut
edges which reduce the distance to three for only one specific $x$-vertex,
there is always one $x$-vertex for which the distance to $u_{i}$ is four,
which contradicts the optimality.

Hence, every $u_{i}$ that is not shortcut to the $x$-vertices is connected to
some set vertex that is shortcut to the $x$-vertices. Additionally, if $u_{i}$
is shortcut to an $x_{j}$ vertex, we can replace that edge by an edge between
the corresponding set vertex and $x_{j}$. So we have constructed a set-cover
of size at most $k$. ∎

We are ready to prove the inapproximability result for BCMD-M. Clearly the
result also holds for the BCMD-$\delta$ problem, as it includes BCMD-M as a
special instance.

######  Lemma 5.

There exists no polynomial-time $(\frac{4}{3}-\epsilon)$-approximation
algorithm for the BCMD-M problem, assuming $\mathbf{P}\neq\mathbf{NP}$.

###### Proof:

Assume that there exists a $(\frac{4}{3}-\epsilon)$-approximation algorithm
$A$ for BCMD-M. We can use algorithm $A$ to decide SetCover, i.e., decide if
there exists a set cover of size at most $k$ to a SetCover instance. If there
is a set cover of size at most $k$, according to Proposition 3 the optimum of
BCMD-M in graph $H$ is at most three. Hence, algorithm $A$ will return a
solution with cost at most $(\frac{4}{3}-\epsilon)3<4$. Because the diameter
only takes integer values, the diameter of the augmented graph is at most
three. On the other hand, if there does not exist a set cover of size at most
$k$, according to Proposition 3 again there is no $k$-augmentation that
reduces the diameter of $H$, and thus, algorithm $A$ will not reduce the
diameter. So we can use algorithm $A$ to decide the SetCover problem, and the
solution returned by algorithm $A$ can be used to recover a solution for
SetCover, in case of a yes-instance. ∎

##  VII Experimental evaluation

In this section we compare and evaluate the practical performance of our three
main algorithms from Section IV. For our first two algorithms, the initial
center vertex (resp., segment) is chosen randomly. We use five real-life
networks, shown in Table I, of varying types, and all with a reasonably large
diameter of their largest connected component.

Since computing the diameter is not feasible for large graphs
($\mathcal{O}(nm)$ time using BFS or
$\mathcal{O}(n^{2.372}\cdot\text{polylog}(n))$ time using matrix
multiplication), we will use the fast heuristic lower bound called 2-Sweep
[22], which has been reported to work very accurately for numerous real-life
networks [24, 22]. The main idea is to pick the farthest vertex from a random
vertex, and return its eccentricity. This heuristic lower bound needs
$\mathcal{O}(m)$ time for connected graphs. The main goal is to compare our
three algorithms against each other, but we also compare with a
straightforward baseline: uniformly at random. This might seem simple, but it
has been reported that random augmentations often perform quite well for
diameter reduction problems [18]. The random algorithm selects uniformly at
random $k$ shortcut non-edges, while respecting a degree increase of at most
$\delta$ per vertex. All experiments are performed on an Intel core i5 machine
at 1.8 GHz with 16 GB RAM. All methods are implemented in Python 3.8 and are
publicly
available.111https://www.dropbox.com/sh/w9h1g2js54rjiy4/AADSsJwlOicUgC2tVk
gdr7Rya?dl=0

(a) Brightkite $(\delta=1)$

(b) Brightkite $(\delta=25)$

(c) Brightkite $(\delta=2^{10})$

(d) Reactome $(\delta=1)$

(e) Reactome $(\delta=25)$

(f) Reactome $(\delta=2^{10})$

(g) Power $(\delta=1)$

(h) Power $(\delta=25)$

(i) Power $(\delta=2^{10})$

(j) Amazon $(\delta=1)$

(k) Amazon $(\delta=25)$

(l) Amazon $(\delta=2^{10})$

(m) roadNet-PA $(\delta=1)$

(n) roadNet-PA $(\delta=25)$

(o) roadNet-PA $(\delta=2^{10})$

Figure 6: The performance of the proposed algorithms for various settings of $k$ and $\delta$. The interruption of the blue colored plot (constant-factor approximation algorithm) indicates that the criterion for the algorithm to run is not fulfilled, as discussed in Section IV-B. TABLE I: Overview of the real-life datasets used in the experiments. For each network, we extracted the largest connected component (LCC). $D$ denotes the diameter. Data (LCC) | Type | $|V|$ | $|E|$ | $D$
---|---|---|---|---
Brightkite [9, 25] | social | 56 739 | 212 945 | 18
Reactome [9, 26] | protein | 5 973 | 145 778 | 24
Power grid [9, 27] | infrastructure | 4 941 | 6 594 | 46
Amazon [28, 29] | co-purchasing | 334 863 | 925 872 | 47
roadNet-PA [28, 30] | road | 1 088 092 | 1 541 898 | 794

(a) roadNet-PA

(b) Amazon

Figure 7: Running time as a function of the number of shortcut edges $k$, on
the Amazon and roadNet-PA datasets.

Influence of $k$ and $\delta$. We test the influence of the number of shortcut
edges $k$ and the degree budget parameter $\delta$ on the performance of the
proposed algorithms. We let $k\in\\{8,16,...,1024\\}$ and
$\delta\in\\{1,25,1024\\}$, where $\delta=1024$ corresponds to an unlimited
degree increase budget (given our range for $k$). For every $k$ and $\delta$,
we repeat each algorithm five times and return the minimum diameter. Results
are shown in Fig. 6. The Greedy 2-Sweep heuristic, the log-approximation and
the constant-factor approximation all significantly perform better than
randomly adding edges. Interestingly, for the Power and roadNet-PA datasets
adding random edges can work well to reduce the diameter, even with a matching
constraint. Another interesting observation is that one does not need a high
degree budget $\delta$ to obtain good diameter reduction. Even with matching
shortcut edges ($\delta=1$), a decent reduction in diameter is often possible.
The difference in results between $\delta=25$ and $\delta=1024$ does not seem
to be that large, but is more noticeable for larger values of $k$. The
interruption of the blue colored plot means that the constant-factor
approximation does not meet the criteria to run. This happens whenever the
largest cluster does not have enough vertices (with enough budget) to shortcut
to the remaining clusters. In Section IV-B we showed that the algorithm is
guaranteed to work if $k\leq\sqrt{\delta n}-1$, but in practice the algorithm
did run for larger values of $k$.

Running time. Fig. 7 shows the running time as a function of $k$ on the two
largest datasets. Doubling the number of edges $k$ roughly leads to doubling
the running time. This corresponds to the $\mathcal{O}(km)$ time complexity of
our methods and the baseline. The influence of $\delta$ on the running time is
negligible.

##  VIII Conclusion and future work

We study the problem of adding $k$ new edges to a graph in order to minimize
its diameter and while respecting degree constraints on the number of edges
added at each vertex. We present three algorithms for this task, and show the
hardness of approximating the problem with ratio better than 4/3. Our paper
opens up several directions for future work. First, an important challenge is
to close the approximability gap between lower and upper bound. A problem
variant, motivated by real-world applications, is to consider non-unit costs
for the new edges to be added.

## Acknowledgment

Both authors are supported by the ERC Advanced Grant REBOUND (834862), the EC
H2020 RIA project SoBigData (871042), and the Wallenberg AI, Autonomous
Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg
Foundation

## References

  * [1] L. Benini and G. De Micheli, “Networks on chips: A new SoC paradigm,” _Computer_ , vol. 35, no. 1, pp. 70–78, 2002.
  * [2] N. Laoutaris, L. J. Poplawski, R. Rajaraman, R. Sundaram, and S.-H. Teng, “Bounded budget connection (BBC) games or how to make friends and influence people, on a budget,” in _Proceedings of the 27th ACM symposium on Principles of distributed computing (PODC)_ , 2008.
  * [3] E. Demaine and M. Zadimoghaddam, “Minimizing the diameter of a network using shortcut edges,” in _SWoAT_ , 2010.
  * [4] A. Meyerson and B. Tagiku, “Minimizing average shortest path distances via shortcut edge addition,” in _Approximation, Randomization, and Comb. Optimization. Algorithms and Techniques_ , 2009, pp. 272–285.
  * [5] R. B. Tan, E. J. Van Leeuwen, and J. Van Leeuwen, “Shortcutting directed and undirected networks with a degree constraint,” _Discrete Applied Mathematics_ , vol. 220, pp. 91–117, 2017.
  * [6] V. Chepoi and Y. Vaxes, “Augmenting trees to meet biconnectivity and diameter constraints,” _Algorithmica_ , vol. 33, no. 2, pp. 243–262, 2002.
  * [7] C. Li, S. McCormick, and D. Simchi-Levi, “On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems,” _Operations Research Letters_ , 1992.
  * [8] D. M. A., W. W. D., H. W. J., and J. W. C., “Cluster of cases of the acquired immune deficiency syndrome. patients linked by sexual contact.” _The American journal of medicine_ , 1984.
  * [9] J. Kunegis, “Konect: The koblenz network collection,” in _22nd Int. Conf World Wide Web_ , 2013, pp. 1343–1350.
  * [10] F. R. K. Chung and M. R. Garey, “Diameter bounds for altered graphs,” _Journal of Graph Theory_ , vol. 8, no. 4, pp. 511–534, 1984.
  * [11] S. H. Bokhari and A. D. Raza, “Reducing the diameters of computer networks,” _IEEE Trans. Comput._ , vol. 35, no. 8, pp. 757–761, 1986.
  * [12] K. Garimella, G. De Francisci Morales, A. Gionis, and M. Mathioudakis, “Reducing controversy by connecting opposing views,” in _Web Search and Data Mining_ , 2017, pp. 81–90.
  * [13] S. Haddadan, C. Menghini, M. Riondato, and E. Upfal, “Repbublik: Reducing polarized bubble radius with link insertions,” in _14th ACM International Conference on Web Search and Data Mining_ , 2021.
  * [14] R. Interian, J. Moreno, and C. Ribeiro, “Polarization reduction by minimum-cardinality edge additions: Complexity and integer programming approaches,” _International Transactions in Operational Research_ , vol. 28, 2020.
  * [15] D. Bilò, L. Gualà, and G. Proietti, “Improved approximability and non-approximability results for graph diameter decreasing problems,” _Theoretical Computer Science_ , vol. 417, pp. 12–22, 2012.
  * [16] Y. Dodis and S. Khanna, “Design networks with bounded pairwise distance,” in _31st annual ACM STOC_ , 1999, pp. 750–759.
  * [17] F. Frati, S. Gaspers, J. Gudmundsson, and L. Mathieson, “Augmenting graphs to minimize the diameter,” _Algorithmica_ , 2015.
  * [18] B. Bollobás and F. R. K. Chung, “The diameter of a cycle plus a random matching,” _SIAM Journal on Discrete Mathematics_ , 1988.
  * [19] Y. Gao, D. R. Hare, and J. Nastos, “The parametric complexity of graph diameter augmentation,” _Discrete Applied Mathematics_ , vol. 161, no. 10, pp. 1626–1631, 2013.
  * [20] M. Dyer and A. Frieze, “A simple heuristic for the p-centre problem,” _Operations Research Letters_ , vol. 3, no. 6, pp. 285–288, 1985. [Online]. Available: https://www.sciencedirect.com/science/article/pii/0167637785900021
  * [21] T. F. Gonzalez, “Clustering to minimize the maximum intercluster distance,” _Theoretical Computer Science_ , vol. 38, pp. 293–306, 1985.
  * [22] C. Magnien, M. Latapy, and M. Habib, “Fast computation of empirically tight bounds for the diameter of massive graphs,” _Journal of Experimental Algorithmics_ , vol. 13, pp. 1–10, 2009.
  * [23] R. M. Karp, _Reducibility among Combinatorial Problems_. Boston, MA: Springer US, 1972, pp. 85–103.
  * [24] P. Crescenzi, R. Grossi, L. Lanzi, and A. Marino, “On computing the diameter of real-world directed (weighted) graphs,” in _International Symposium on Experimental Algorithms_ , 2012, pp. 99–110.
  * [25] E. Cho, S. A. Myers, and J. Leskovec, “Friendship and mobility: User movement in location-based social networks,” in _Proceedings of the 17th ACM SIGKDD KDD_ , 2011.
  * [26] G. Joshi-Tope, M. Gillespie, I. Vastrik, P. D’Eustachio, E. Schmidt, B. de Bono, B. Jassal, G. Gopinath, G. Wu, L. Matthews _et al._ , “Reactome: a knowledgebase of biological pathways,” _Nucleic Acids Research_ , vol. 33, pp. D428–D432, 2005.
  * [27] D. J. Watts and S. H. Strogatz, “Collective dynamics of small-world networks,” _Nature_ , vol. 393, no. 6684, pp. 440–442, 1998.
  * [28] J. Leskovec and A. Krevl, “SNAP Datasets,” http://snap.stanford.edu/data, Jun. 2014.
  * [29] J. Yang and J. Leskovec, “Defining and evaluating network communities based on ground-truth,” _Knowledge and Information Systems_ , vol. 42, no. 1, pp. 181–213, 2015.
  * [30] J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, “Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters,” _Internet Mathematics_ , 2009.