Reinhard Bauer
email: reinhard.bauer@kit.edu

Gianlorenzo D'angelo
email: gianlorenzo.dangelo@univaq.it

Daniel Delling
email: dadellin@microsoft.com

Andrea Schumm
email: andrea.schumm@kit.edu

Dorothea Wagner
email: dorothea.wagner@kit.edu

The Shortcut Problem -Complexity and Algorithms ⋆

We study a graph-augmentation problem arising from a technique applied in recent approaches for route planning. Many such methods enhance the graph by inserting shortcuts, i.e., additional edges (u, v) such that the length of (u, v) is the distance from u to v. Given a weighted, directed graph G and a number c ∈ Z >0 , the shortcut problem asks how to insert c shortcuts into G such that the expected number of edges that are contained in an edge-minimal shortest path from a random node s to a random node t is minimal. In this work, we study the algorithmic complexity of the problem and give approximation algorithms for a special graph class. Further, we state ILP-based exact approaches and show how to stochastically evaluate a given shortcut assignment on graphs that are too large to do so exactly.

Contribution. In this work, we formally state the SHORTCUT PROBLEM and a variant of it, the REVERSE SHORTCUT PROBLEM. While we study the algorithmic complexity of both problems, the algorithmic contribution focuses on the SHORTCUT PROBLEM. We state exact, ILP-based solution approaches. We further describe two algorithms that give approximation guarantees on graphs in which, for each pair s,t of nodes, there is at most one shortest s-t-path. It turns out ⋆ Partially supported by the DFG (project WA654/16-1). that this class is highly relevant as in road networks, most shortest paths are unique and only small modifications have to be made to obtain a graph having unique shortest paths. Finally, we show how to stochastically evaluate a given shortcut assignment on graphs that are too large to do so exactly. Besides its relevance as a step towards theoretical results on speedup-techniques, we consider the problem to be interesting and beautiful on its own right.

 experimentally examines heuristic algorithms to find shortcut assignments with high quality, including local search strategies and a betweenness-based approach. Furthermore, the GREEDY-step Algorithm 3 is proposed in this thesis. To the best of our knowledge, the problem of finding shortcuts as stated in this work has never been treated before.

 and Contraction Hierarchies [13] use a similar strategy.

Overview. This paper is organized as follows. Section 2 introduces basic definitions. The SHORT-CUT PROBLEM and the REVERSE SHORTCUT PROBLEM are stated in Section 3. Furthermore, results concerning complexity and non-approximability of the problems are given. The remainder of the paper focuses on the SHORTCUT PROBLEM. Section 4 proposes two exact, ILP-based approaches. In Section 5, a greedy algorithm is presented that gives an approximation guarantee on graphs in which shortest paths are unique. Section 6 states an approximation algorithm that works on graphs with bounded degree in which shortest paths are unique. A probabilistic approach to evaluate a given solution of the SHORTCUT PROBLEM is introduced in Section 7. The paper is concluded by a summary and possible future work in Section 8.

Introduction

Background. Computing shortest paths in graphs is used in many real-world applications like route-planning. Shortest paths from a given source to a given target can be computed by DIJK-STRA'S algorithm, but the algorithm is slow on huge datasets. Therefore, it can not be directly used for applications like car navigation systems or online working route-planners that require an instant answer to a source-target query. In the last decade various preprocessing-based techniques have been developed that yield much faster query-times (see [START_REF] Sanders | Engineering Fast Route Planning Algorithms[END_REF][START_REF] Wagner | Speed-Up Techniques for Shortest-Path Computations[END_REF] for an overview).

One core part of some of these approaches is the insertion of shortcuts [7, 9, 13-15, 20, 24, 26, 28, 29], i.e., additional edges (u, v) whose length is the distance from u to v and that represent shortest u-v-paths in the graph. The strategies of assigning the shortcuts and of exploiting them during the query differ depending on the speedup-technique. Many techniques work as follows: In a preprocessing stage, the nodes of the input graph are assigned to a level and shortcuts are added to the graph. Afterwards, the query stage is similar to bidirectional Dijkstra's algorithm but omits -depending on the level -some edges. However, it is still guaranteed that correct distances are computed. Until now, all existing shortcut insertion strategies are heuristics and only few theoretical worst-case or average case results are known [START_REF] Abraham | Highway Dimension, Shortest Paths, and Provably Efficient Algorithms[END_REF][START_REF] Bauer | Preprocessing Speed-Up Techniques is Hard[END_REF].

In this context, an interesting new theoretical problem arises: Given a weighted, directed graph G and a number c ∈ Z >0 , the shortcut problem asks how to insert c shortcuts into G such that the expected number of edges that are contained in an edge-minimal shortest path from a random node s to a random node t is minimal.

Preliminaries

Let A ⊆ X be a subset of a set X. The indicator function of A and X is the function 1 A : X → {0, 1} defined as 1 A (x) = 1 if x ∈ A and 1 A (x) = 0 otherwise.

Common Graph Theory. Throughout this work, G = (V, E, len) denotes a directed, weighted graph with positive length function len : E → R >0 . Given nodes u and v, we call u a neighbor of v if there is an edge (u, v) or (v, u). We denote by N(v) the set of all neighbors of v. Given a set S of nodes, the neighborhood of S is the set S ∪ u∈S N(u).

We denote by ← -G the reverse graph of G, i.e. the graph (V,

← - E , ← - len) with ← - E := {(v, u) | (u, v) ∈ E} and
←len being defined by ←len(u, v) := len(v, u) for (v, u) ∈ E. A path P from x 1 to x k in G is a finite sequence (x 1 , x 2 , . . . , x k ) of nodes such that (x i , x i+1 ) ∈ E, i = 1, . . . , k -1 and x i = x j for each i = j. We say P contains an edge (u, v) if (u, v) = (x i , x i+1 ) for some i ∈ {1, . . . , k -1} and use the abbreviation (u, v) ∈ P. The length len(P) of P is the sum of the lengths of all edges in P, i.e. len(P) = ∑ k-1 i=1 len(x i , x i+1 ). A shortest path from node s to node t is a path from s to t of minimum length. Given two nodes s and t the distance dist(s,t) from s to t is the length of a shortest path from s to t and ∞ if there is no path from s to t. The diameter of a graph G is the largest distance in G, i.e. max{dist(s,t) | s,t ∈ V }. The eccentricity ε G (v) of a node v is the maximum distance between v and any other node u of G.

A cycle is a finite sequence (x 1 , x 2 , . . . , x k ) of nodes such that (x i , x i+1 ) ∈ E, i = 1, . . . , k -1 and x i = x k . A (rooted) tree with root (node) s is a directed graph T = (V ′ , E ′ ) without cycles such that for each node t ∈ V ′ there is exactly one path from s to t. We call v a descendant of t in T , if the path from s to v in T contains t. Note that each node is a descendant of itself.

A shortest-paths tree with root s is a subgraph T = (V ′ , E ′ ) of G such that T is a tree, V ′ is the set of nodes reachable from s and such that for each edge (u, v) ∈ E ′ we have dist(s, u)+len(u, v) = dist(s, v). Note that each path in T is a shortest path. The shortest-path subgraph with root s is the subgraph G s = (V ′ , E ′′ ) of G such that V ′ is the set of nodes reachable from s and E ′′ is the set of all edges with dist(s, u) + len(u, v) = dist(s, v). Note that G s contains exactly all shortest-paths in G that start with s. Further, G s is directed acyclic in case all edge weights are strictly positive. Specific Notation and Considered Graphs. Consider a path P = (x 1 , x 2 , . . . , x k ). We say P contains node u before node v if there are numbers i, j with 0 ≤ i ≤ j ≤ k such that u = x i and v = x j .

Given is a sequence y 1 , . . . , y k for k ≥ 2. A y 1 -y 2 -. . .-y k -path is a path P from y 1 to y k such that P contains node y i before node y i+1 for i = 1, . . . , k -1. A shortest y 1 -y 2 -. . .-y k -path is a y 1 -y 2 -. . .y k -path that is a shortest path from y 1 to y k . Let P -(x, y) := {s ∈ V | ∃ shortest s-y-path containing x} P + (x, y) := {t ∈ V | ∃ shortest x-t-path containing y} denote the sets of start-or end-vertices of shortest paths through x and y. Similarly, let P(x, y) := {(s,t) ∈ V ×V | ∃ shortest s-t-path that contains x before y} consist of all pairs of nodes, for which a connecting shortest path containing first x and then y exists. Finally, let P ⊲⊳ (x, y) := {u ∈ V | ∃ shortest x-y-path that contains u} be the set of all nodes that lie on a shortest x-y-path.

We call a graph G sp-unique if, for any pair of nodes s and t in G, there is at most one, unique shortest s-t-path in G. Let P = (x 1 , x 2 , . . . , x k ) be a path. The hop-length |P| of P is k -1. Given two nodes s and t, the hop-distance h G (s,t) from s to t is the minimum hop-length of any shortest s-tpath in G and 0 if there is no s-t-path in G or if s = t. We abbreviate h G (s,t) by h(s,t) if the choice of the graph G is clear. We further assume that for each edge

(u, v) in G it is len(u, v) = dist(u, v).
This can easily be assured by deleting edges (u, v) with len(u, v) > dist(u, v) in a preprocessing step. This guarantees that, after the insertion of a shortcut (a, b), there is only one edge (a, b) in the graph.

Problem Statement and Complexity

In this section, we introduce the SHORTCUT PROBLEM and the REVERSE SHORTCUT PROB-LEM. We show that both problems are NP-hard. Moreover, we show that there is no polynomialtime constant-factor approximation algorithm for the REVERSE SHORTCUT PROBLEM and no polynomial-time algorithm that approximates the SHORTCUT PROBLEM up to an additive constant unless P = NP. Finally, we identify a critical parameter of the SHORTCUT PROBLEM and discuss some monotonicity properties of the problem.

In the following, we augment a given graph G with shortcuts. These are edges (u, v) that are added to G such that len(u, v) = dist(u, v). A set of shortcuts is called a shortcut assignment.

Definition (Shortcut Assignment). Consider a graph G = (V, E, len). A shortcut assignment for G is a set E ′ ⊆ (V × V ) \ E such that, for any (u, v) in E ′ , it is dist(u, v) < ∞. The notation G[E ′ ]
abbreviates the graph G with the shortcut assignment E ′ added, i.e., the graph (V, E ∪ E ′ , len ′ )

where len ′ : E ∪ E ′ → R >0 equals dist(u, v) if (u, v) ∈ E ′ and equals len(u, v) otherwise.
When working with shortcuts we are interested in the expected number of edges that are contained in an edge-minimal shortest path from a random node s to a random node t. The gain of a shortcut assignment E ′ measures how much this value decreases due to the graph-augmentation with E ′ . Definition (Gain). Given a graph G = (V, E, len) and a shortcut assignment

E ′ , the gain w G (E ′ ) of E ′ is w G (E ′ ) := ∑ s,t∈V h G (s,t) -∑ s,t∈V h G[E ′ ] (s,t) .
We abbreviate w G (E ′ ) by w(E ′ ) in case the choice of the graph G is clear.

We briefly consider an augmented graph G[E ′ ] = (V, E ∪ E ′ , len ′ ) and choose nodes s and t uniformly at random. The expected number of edges on an edge-minimal shortest s-t-path is

1 |V | 2 ∑ s,t∈V h G[E ′ ]
(s,t) when we count pairs s and t with dist(s,t) = ∞ by 0. The term ∑ s,t∈V h G (s,t) does not depend on E ′ and hence is constant. Consequently, maximizing the gain and minimizing the expected number of edges on edge-minimal shortest-paths are equivalent problems. The SHORTCUT PROBLEM consists of adding a number c of shortcuts to a graph, such that the gain is maximal.

Problem (SHORTCUT PROBLEM)

. Let G = (V, E, len) be a graph and c ∈ Z >0 be a positive integer. Given an instance (G, c), the SHORTCUT PROBLEM is to find a shortcut assignment

E ′ with |E ′ | ≤ c such that the gain w G (E ′ ) of E ′ is maximal.
The REVERSE SHORTCUT PROBLEM searches for a shortcut assignment E ′ of minimum cardinality achieving at least some given gain k. We assure that such a solution exists by stating an upper bound on k. To obtain k, we first compute the number

{(u, v) ∈ V ×V | dist(u, v) < ∞, u = v} .

This is exactly the value of ∑ s,t∈V h G[S]

(s,t) when inserting all possible shortcuts S to G. Then we subtract this value from ∑ s,t∈V h G (s,t) to yield a sharp bound on the gain.

Problem (REVERSE SHORTCUT PROBLEM).

Let G = (V, E, len) be a graph and k ∈ Z >0 be less

than or equal to ∑ s,t∈V h G (s,t) -|{(u, v) ∈ V ×V | dist(u, v) < ∞, u = v}|. Given an instance (G, k) the REVERSE SHORTCUT PROBLEM is to find a shortcut assignment E ′ such that w G (E ′ ) ≥ k and such that |E ′ | is minimal.
As an auxiliary problem to shorten proofs we also consider the SHORTCUT DECISION PROBLEM.

Problem (SHORTCUT DECISION PROBLEM).

Let G = (V, E, len) be a graph and c, k ∈ Z >0 be positive integers. Given an instance (G, c, k), the SHORTCUT DECISION PROBLEM is to decide if there is a shortcut assignment

E ′ for G = (V, E, len) such that w G (E ′ ) ≥ k and |E ′ | ≤ c.
In order to show the complexity of the problems we make a transformation from SET COVER and MIN SET COVER.

Definition (SET COVER and MIN SET COVER).

Let C be a collection of subsets of a finite set U such that c∈C c = U and let k ∈ Z >0 be a positive integer. A set cover of (C,U) is a subset C ′ of C such that every element in U belongs to at least one member of C ′ . Given an instance (C,U), the problem MIN SET COVER is to find a set cover C ′ of (C,U) of minimum cardinality. Given an instance (C,U, k), the problem SET COVER is to decide if there is a set cover C ′ of (C,U) of cardinality no more than k. The size of a MIN SET COVER instance (C,U) is ∑ c∈C |c|.

Notation (Solution). Given a {SHORTCUT PROBLEM, REVERSE SHORTCUT PROBLEM, MIN SET COVER}-instance I, we denote by opt {SP,RSP,MSC} (I) an arbitrary (optimal) solution of I of the according problem.

We now show a relationship between SET COVER and the SHORTCUT PROBLEM.

Lemma 1. Let (C,U, k) be a SET COVER-instance. Then, there is a graph G = (V, E, len) such that there is a set cover C ′ for (C,U) of cardinality |C| ′ ≤ k if, and only if there is a shortcut assignment E ′ for G of cardinality |E| ′ ≤ k and gain w(E ′ ) ≥ (2|C| + 1)|U|. Further, the size of G and the time to compute G is polynomial in the size of (C,U). Finally, given a shortcut assignment E ′ with w(E ′ ) ≥ (2|C| + 1)|U|, we can compute a set cover of cardinality at most |E ′ | in time polynomial in the size of (C,U, k).

Proof. Given an instance (C,U, k) of SET COVER, we construct the graph G = (V, E, len) as follows, see Figure 1 for an illustration: We denote the value 2|C| + 1 by ∆ . We introduce a node s to G. For each u ∈ U, we introduce a set of nodes U u = {u 1 , . . . , u ∆ } to G. For each c in C, we introduce nodes c -, c + and edges (c -, c + ), (c + , s) to G. The graph furthermore contains, for each u ∈ U and each c ∈ C with u ∈ c, the edges (u r , c -), r = 1, . . . , ∆ . All edges are directed and have length 1. We abbreviate U := u∈U U u , C -:= {c -|c ∈ C} and

C + := {c + |c ∈ C}. c + 1 c - 1 c + 2 c - 2 c + 3 c - 3 U 1 U 2 U 3 U 4 U C - C + s {s} Fig. 1: Graph G = (V, E) constructed from the SET COVER-instance {c 1 = {1, 2}, c 2 = {2, 3}, c 3 = {3, 4}}.
We first observe that shortcuts in G are always contained in one of the following three sets:

U × {s},C -× {s} and U ×C + . Given u ∈ U, we say u is covered by a shortcut (c -, s) ∈ C -× {s} if u ∈ c.
Claim. Let C ′ be a set cover of (C,U). Then, the shortcut assignment

E ′ = {(c -, s) | c ∈ C ′ } fulfills |E ′ | = |C ′ | and w(E ′ ) ≥ ∆ |U|.
Obviously |E ′ | = |C ′ | holds. For each node v ∈ U the hop-distance to node s decreases by 1 due to the insertion of

E ′ . As |U| = ∆ |U|, it is w(E ′ ) ≥ ∆ |U|. Claim. Let E ′ be a shortcut assignment of G with w(E ′ ) ≥ ∆ |U|. Then, we can construct a shortcut assignment E ′′ ⊆ C -× {s} of G with cardinality |E ′′ | ≤ |E| and w(E ′′ ) ≥ ∆ |U| in polynomial time. We first check if |E ′ | > |C|.
If this is the case, we set E ′′ := {(c -, s)|c ∈ C} and terminate. Otherwise, we proceed as follows until E ′ ⊆ C -× {s} or each u ∈ U is covered by a shortcut (c -, s): We choose a shortcut (x, y) in E ′ ∩ (U × C + ∪ U × {s}). We further choose a shortcut (c -, s) ∈ V ×V such that there is a u ∈ c which is not covered by any shortcut in E ′ . Then, we set

E ′ := (E ′ ∪ {(c -, s)}) \ {(x, y)}.
The removal of a shortcut in U × C + ∪ U × {s} decreases the gain by at most 2. Let u ∈ U be an element that is not covered by a shortcut in E ′ and let u ∈ c ∈ C. The insertion of (c -, s) in E ′ improves the hop distance h(v, s) for each node in v ∈ U u which is not part of a shortcut in E ′ by 1. As there are 2|C| + 1 nodes in U u and we have at most |C| shortcuts, the gain increases by at least 2|C| + 1 -|C|. Summarizing, at each step w(E ′ ) increases at least by 2|C| + 1 -|C| -2 = |C| -1 ≥ 0. Any shortcut assignment that covers all u ∈ U results in the desired gain. Hence, after termination E ′′ := E ′ ∩ (C -× {s}) gives a solution to the claim.

Claim. Let E ′ be a shortcut assignment of G with w(E ′ ) ≥ ∆ |U|. Then, we can compute in polynomial time a set cover C ′ for (C,U) of cardinality at most |E ′ |.

We use the last claim to transform

E ′ such that E ′ ⊆ C -× {s} and w(E ′ ) ≥ ∆ |U|. It is w(E ′ ) = |E ′ |+∆ |{u ∈ U | u is covered by a shortcut in E ′ }| ≥ ∆ |U|. This implies that each u ∈ U is covered by a shortcut in E ′ and {c|(c -, s) ∈ E ′ } is a set cover of (C,U). Theorem 1. The SHORTCUT DECISION PROBLEM is NP-complete.
Proof. Let (C,U, k) be a SET COVER-instance and G be constructed as described in Lemma 1. It is (C,U, k) a yes-instance if and only if the SHORTCUT DECISION PROBLEM-instance (G, |k|, (|2|C|+ 1)|U|) is a yes-instance, and the transformation is polynomial.

We remember that an optimization problem P is NP-hard if there is an NP-hard decision problem P ′ such that following holds: Problem P ′ can be solved by a polynomial-time algorithm which uses an oracle that, for any instance of P, returns -in constant time-an optimal solution along with its value.

Corollary. The SHORTCUT PROBLEM and the REVERSE SHORTCUT PROBLEM are NP-hard.

The transformation applied in Lemma 1 also preserves part of the non-approximability of MIN SET COVER.

Theorem 2. Unless P = NP, no polynomial-time constant-factor approximation algorithm exists for the REVERSE SHORTCUT PROBLEM, i.e., there is no combination of an algorithm apx and an approximation ratio α > 0 such that

-apx(G, k) is a shortcut assignment for G of gain at least k -| apx(G, k)|/| opt RSP (G, k)| ≤ α for all instances (G, k) of the REVERSE SHORTCUT PROBLEM -the runtime of apx(G, k) is polynomial in the size of (G, k).
Proof. Given a MIN SET COVER-instance (C,U), assume to the contrary that there is a polynomialtime constant-factor approximation apx of the REVERSE SHORTCUT PROBLEM with approximation ratio α. Using apx, we construct a constant-factor approximation algorithm for MIN SET COVER, contradicting the fact that MIN SET COVER is not contained in the class APX unless P = NP [START_REF] Ausiello | Complexity and Approximation -Combinatorial Optimization Problems and Their Approximability Properties[END_REF]:

As described in Lemma 1, we first construct the graph G. Then we compute E ′ = apx(G, (2|C|+ 1)|U|) and finally transform E ′ to a set cover C ′ of (C,U) of size at most |E ′ |. With Lemma 1 we have that

| opt MSC (C,U)| = | opt RSP (G, (2|C| + 1)|U|)| .
Hence it is

|C ′ |/| opt MSC | ≤ |E ′ |/| opt RSP (G, (2|C| + 1)|U|)| ≤ α
which shows the theorem.

Using a stronger result on the inapproximability of the MIN SET COVER-problem, we get an asymptotically tighter lower bound on the approximation factor of the REVERSE SHORTCUT PROBLEM.

Proposition. Unless P = NP, no polynomial-time algorithm exists that approximates the RE-VERSE SHORTCUT PROBLEM to a factor Ω log(log |V |) .

Proof. By [START_REF] Alon | Algorithmic construction of sets for k-restrictions[END_REF], MIN SET COVER is not approximable within a factor η • ln |U|, for a certain constant η. Assume that there is a polynomial-time approximation algorithm apx for the REVERSE SHORTCUT PROBLEM such that

| apx(G, k)|/| opt RSP (G, k)| ≤ η • ln log(|V |) 2 -2 for all instances (G = (V, E), k) of the REVERSE SHORTCUT PROBLEM.
Let (C,U) be an arbitrary instance of MIN SET COVER. Analogous to the proof of Theorem 2, we construct a graph G = (V, E) with (2|C| + 1)|U| + 2|C| + 1 nodes and a set cover

C ′ in polynomial-time such that |C ′ |/| opt MSC (C,U)| ≤ η • ln log(|V |) 2 -2 .
Our goal is to obtain an upper bound on log(|V |) depending on |U|, thus we aim to get an upper bound on |V | in the form 2

x . As |C| ≤ 2 |U| and |U| ≤ 2 |U| , it is |V | ≤ (2 |U|+1 +1)|U|+2 |U|+1 +1 ≤ (2 |U|+1 +1)2 |U|+1 +2 |U|+1 +1 = 2 2|U|+2 +2 |U|+2 +1 ≤ 2 2|U|+4 Hence, it is 2|U| + 4 ≥ log(|V |) and thus |C ′ |/| opt MSC (C,U)| ≤ η • ln |U|, contradicting the inap- proximability of MIN SET COVER.
Theorem 3. Unless P = NP, no polynomial-time algorithm exists that approximates the SHORT-CUT PROBLEM up to an additive constant, i.e., there is no combination of an algorithm apx and a

maximum error α ∈ R >0 such that -apx(G, c) is a shortcut assignment for G of cardinality at most c -the runtime of apx(G, c) is polynomial in the size of (G, c) -w G (opt SP (G, c)) -w G (apx(G, c)) ≤ α for all instances (G, c) of the SHORTCUT PROBLEM.
Proof. Assume to the contrary that there is an polynomial-time algorithm apx that approximates the SHORTCUT PROBLEM up to an additive constant maximum error α and let (G = (V, E, len), c, k) be a SHORTCUT DECISION PROBLEM-instance. To assure α ∈ Z + , we set α := ⌈α⌉. We construct

an instance (G = (V , E, len), c) of the SHORTCUT PROBLEM by adding to G, for each node v ∈ V , exactly χ := α + 1 + |V | 2 nodes v 1 , . . . , v χ and directed edges (v 1 , v), . . . , (v χ , v). We further set len(v i , v) = 1 for i = 1 . . . χ. This construction can be done in polynomial time. Let E ′ denote apx(G, c).
Our aim is to solve (G = (V, E, len), c, k) in polynomial time. We can insert at most

c max := |{(u, v) ∈ V ×V \ E| dist(u, v) < ∞, u = v}| shortcuts into G. If c ≥ c max
we can decide the problem in polynomial time by adding all possible shortcuts and computing the according gain. Hence, in the following we may assume c < c max .

Claim. The endpoints of all shortcuts inserted by apx in

G lie in V , i.e E ′ ⊆ V ×V . If a shortcut in G is not contained in V × V , it must be contained in V × V because of the edge directions in G. Assume that there is a shortcut (u, v) ∈ E ′ such that (u, v) ∈ (V \ V ) × V .
Removing (u, v) from E ′ will decrease the gain w G (E ′ ) by at most |V | 2 (as it represents only paths starting from u of length at most |V | + 1). Afterwards inserting an arbitrary shortcut (x, y) ∈ V ×V increases the gain w G (E ′ \ {(u, v)}) by at least χ (as it represents at least χ paths ending at y of length at least 2). Summarizing,

w G (({(x, y}) ∪ E ′ ) \ {(u, v)}) -w G (E ′ ) ≥ χ -|V | 2 > α
contradicting the approximation guarantee of apx.

Claim. We can use apx to decide (G = (V, E, len), c, k) in polynomial time contradicting the assumption P = NP.

An exact algorithm can be seen as an approximation algorithm with maximum error α = 0. We can show in a similar fashion as in the last claim that an optimal solution of (G, c) only consists of shortcuts in

V × V , i.e., opt SP (G, c) ⊆ V × V . Given a shortcut assignment E ′′ ∈ V × V , it is w G (E ′′ ) = (1 + χ) • w G (E ′′ ).
Given an optimal solution E * for (G, c) and (G, c), it follows

(1 + χ) w G (E * ) -w G (E ′ ) = w G (E * ) -w G (E ′ ) ≤ α. Hence, w G (E * ) -w G (E ′ ) ≤ α/(1 + χ) < 1 which implies w G (E * ) = w G (E ′ ) as both w G (E *
) and w G (E ′ ) are integer valued. This shows the claim and finishes the proof.

To obtain a better intuition on the SHORTCUT PROBLEM, we report some properties of the problem.

Trivial approximation bounds. Consider an arbitrary non-empty shortcut assignment E

′ . It is 0 ≤ ∑ s,t∈V h G (s,t) ≤ |V | 3 for any graph G = (V, E, len) and hence w G (E ′ ) ≤ |V | 3 .
As each shortcut in E ′ decreases the hop-distance from its start to its end-node by at least one 1 we have that each E ′ is a trivial factor |V | 3 /|E ′ |-approximation of the SHORTCUT PROBLEM. Further, any shortcut assignment achieving the desired gain is a trivial factor |V | 2 -approximation of the REVERSE SHORTCUT PROBLEM.

Bounded number of shortcuts. If the number of shortcuts we are allowed to insert is bounded by a constant k max , the number of possible solutions of the SHORTCUT PROBLEM is at most

|V | 2 k max = |V | 2 ! (|V | 2 -k max )!k max ! ≤ |V | 2k max .
This is polynomial in the size of the input graph G = (V, E, len). We can evaluate a given shortcut assignment by basically computing all-pairs shortest-paths, hence this can be done in time

O(|V | 2 log |V | + |V ||E|) using Dijkstra's algorithm.
For this reason, the case with bounded number of shortcuts can be solved in polynomial time by a brute-force algorithm.

Monotonicity. In order to show the hardness of working with the problem beyond the complexity results, Figure 2 gives an example that, given a shortcut assignment S and an additional shortcut s ∈ S, the following two inequalities do not hold in general:

w(S ∪ {s}) ≥ w(S) + w(s) (1) w(S ∪ {s}) ≤ w(S) + w(s). ( 2
)
It is easy to verify that in Figure 2 the inequalities w({s 1 , s 2 }) > w(s 1 )+w(s 2 ) and w({s

1 , s 2 , s 3 }) < w({s 1 , s 2 }) + w(s 3 ) hold.
Note that Inequality 2 holds if, for any pair of nodes (s,t) of graph G, there is at most one, unique shortest s-t-path in G. We call such a graph sp-unique and prove that fact in the following lemma. Lemma 2. Given an sp-unique graph G = (V, E, len) and a set of shortcuts S = {s 1 , s 2 , . . . ,

s k }. Then, w G (S) ≤ ∑ k i=1 w G (s i ) and w G (S) ≤ w G ({s 1 , . . . s k-1 }) + w G (s k ).
Proof. Given arbitrary but fixed a, b ∈ V we denote by w ab G (S) the gain of S on graph G restricted to shortest a-b-paths, i.e., w ab

G (S) = h G (a, b) -h G[S] (a, b). Because of w G (S) = ∑ u,v∈V w uv G (S) it suffices to show w ab G (S) ≤ w ab G ({s 1 , . . . s k-1 }) + w ab G (s k ).
The inequality w ab G (S) ≤ ∑ k i=1 w ab G (s i ) then follows by induction. We write s k = (x, y). It is

w ab G (S) = w ab G ({s 1 , . . . , s k-1 }) + w ab G[s 1 ,...,s k-1 ] ({(x, y)}).
If (a, b) ∈ P(x, y), we have

w ab G[s 1 ,...,s k-1 ] ({(x, y)}) ≤ h G[s 1 ,...,s k-1 ] (x, y) -1 ≤ h G (x, y) -1 = w ab G (s k ). Further, if (a, b) ∈ P(x, y) we have w ab G[s 1 ,...,s k-1 ] ({(x, y)}) = 0 = w ab G (s k ).
Hence, we have

w ab G (S) ≤ w ab G ({s 1 , . . . s k-1 }) + w ab G (s k )
which shows the lemma.

Later, we use these results to present an approximation algorithm for sp-unique graphs.

ILP-Approaches

In this section we present two exact, ILP-based approaches for the SHORTCUT PROBLEM. Throughout this section, we are given an instance (G = (V, E, len), c) of the SHORTCUT PROBLEM that is to be solved optimally. For a vertex x ∈ V , we denote by P x the set of all vertices u ∈ V for which an x-u-path exists. Remember that we denote by P + (x, y) the set of all vertices u ∈ V for which a shortest x-u path containing y exists and that we denote by P ⊲⊳ (x, y) the set of all vertices that lie on a shortest x-y-path. We assume that all distances in the graph are precomputed and hence that the sets P x , P ⊲⊳ (x, y) and P + (x, y) are known for all x, y ∈ V .

Simple ILP-Formulation. The following ILP-formulation (SLSP) is straightforward and simple but has the drawback to incorporate O(|V | 4 ) variables and constraints. The interpretation of the ILP is as follows: The variables k s t (•, •) represent an edge-minimal shortest s-t-path in the augmented graph. It is k s t (u, v) = 1 if and only if the edge (u, v) is used in this path. We characterize all edges or possible shortcuts (u, v) that can be used for a shortest s-t-path by introducing the set

A := {(s, u, v,t) ∈ V 4 | dist(s, u) + dist(u, v) + dist(v,t) = dist(s,t) < ∞, u = v}.
Consequently, for fixed s, v,t ∈ V , the set {u ∈ V | (s, u, v,t) ∈ A} contains each node u such that the edge or shortcut (u, v) can be used in a shortest s-t-path. The variable c(u, v) equals 1 if the computed shortcut assignment contains (u, v). Instead of maximizing the gain, our aim is to minimize the sum of all hop-distances in the augmented graph. This value equals the sum of all variables k s t (u, v) with (s, u, v,t ∈ A).

(SLSP) minimize ∑ (s,u,v,t)∈A k s t (u, v) (3) such that ∑ {v∈V |(s,v,t,t)∈A} k s t (v,t) = 1 s ∈ V, t ∈ P s \ {s} (4) ∑ {u∈V |(s,u,v,t)∈A} k s t (u, v) = ∑ {w∈V |(s,v,w,t)∈A} k s t (v, w) s ∈ V, t ∈ P s \ {s} v ∈ P ⊲⊳ (s,t), v = s,t (5)
k s t (u, v) ≤ c(u, v) (s, u, v,t) ∈ A, (u, v) ∈ E (6) ∑ (u,v)∈(V ×V )\E c(u, v) ≤ c (7) k s t (u, v) ∈ {0, 1} (s, u, v,t) ∈ A (8) c(u, v) ∈ {0, 1} (u, v) ∈ V ×V \ E (9)
Constraint 4 and Constraint 5 ensure that a shortest path is considered for every s-t-pair: Constraint 4 requires that each target t owns exactly one incoming edge on an s-t-path while Constraint 5 guarantees that, for each node v = s,t, there is an incoming edge (on an s-t-path) if there is an outgoing edge (on such a path). Constraint 6 forces shortcuts to be present whenever edges are used that are not present in the graph. Finally, Constraint 7 limits the number of shortcuts to be inserted. Consequently, a solution of model (SLSP) gives an optimal solution of (G, c):

The set {(u, v) ∈ V × V |c(u, v) = 1}
is a shortcut assignment for G of maximum gain and cardinality at most c.

Obviously, there can be more than one edge-minimal shortest path from a given source to a given target. Hence, the model may incorporate unwanted symmetries. In order to break these symmetries one could use additional constraints. We did not further pursue this direction because of the huge number of constraints that would be necessary. Note that the model stays correct when relaxing Constraint 8 to

k s t (u, v) ∈ [0, 1] (s, u, v,t) ∈ A.
Flow-Based ILP-Formulation. The number of variables and constraints of the following integer linear program (LSP) is cubic in |V |. The model exhibits two types of variables. It is c(u, v) = 1 if and only if the solution found uses the shortcut (u, v). Instead of directly counting the hop-distance for each pair of nodes, we use a flow-like formulation that counts, for each edge, how often it is used in the solution. In detail, the value of f s (u, v) can be interpreted as the number of vertices t for which the hop-minimal shortest s-t-path found by (LSP) includes the edge or shortcut (u, v). To characterize all possible combinations of s, u, v ∈ V such that (u, v) could be an edge or a shortcut in the shortest-paths subgraph with root s, we introduce the set

B := {(s, u, v) ∈ V 3 | dist(s, u) + dist(u, v) = dist(s, v) < ∞, u = v} .
The flow outgoing from source s is exactly the number of vertices reachable from s (Constraint 11).

As each node consumes exactly one unit of flow (Constraint 12), it is assured that a shortest path from s to any reachable node is considered. Constraint 13 forces shortcuts to be present whenever edges are used that are not present in the graph. Finally, Constraint 14 limits the number of shortcuts to be inserted. Again, instead of maximizing the gain, our aim is to minimize the sum of all hop-distances in the augmented graph which is given as obj( f , c).

(LSP) minimize obj( f , c) := ∑ (s,u,v)∈B f s (u, v) (10)
such that

∑ {v∈V |(s,s,v)∈B} f s (s, v) = |P s | -1 s ∈ V (11) ∑ {u∈V |(s,u,v)∈B} f s (u, v) = 1 + ∑ {w∈V |(s,v,w)∈B} f s (v, w) s ∈ V, v ∈ P s , v = s ( 12
)
f s (u, v) ≤ |P + (s, v)| • c(u, v) (s, u, v) ∈ B, (u, v) ∈ E, (13)
∑ (u,v)∈(V ×V )\E c(u, v) ≤ c ( 14
)
f s (u, v) ∈ Z ≥0 (s, u, v) ∈ B (15) c(u, v) ∈ {0, 1} (u, v) ∈ V ×V \ E ( 16
)
We now prove the correctness of model (LSP). The proof of the following preparatory lemma shows that a solution of (LSP) can be converted into a solution of equal objective value that, for each node, induces a shortest-paths tree.

Lemma 3. There exists an optimal solution ( f , c) of (LSP), such that for each s ∈ V , the subgraph induced by

T s := {(u, v) ∈ V ×V | f s (u, v) > 0} is a tree.
Proof. Let ( f , c) be a solution of (LSP). Then T s is a directed acyclic graph with root s as T s is contained in the shortest-paths subgraph of G with root s. As long as T s is not a tree proceed as follows:

First, consider an arbitrary node y such that there are two edges (v, y) and (w, y) in T s . Let x be an arbitrary node such that there are disjoint x-y-paths P 1 and P 2 in T s . Such a node x has to exist as there is more than one shortest s-y-path in T s and we can take any topologically maximal node x for which there is more than one x-y-path. Let (y ′ , y) be the last edge on P 1 and ∆ := f s (y ′ , y). For each edge e on P 1 we set f s (e) := f s (e) -∆ , for each edge e on P 2 we set f s (e) := f s (e) + ∆ .

It is easy to verify that this does not change the feasibility of the solution. Obviously, the objective function cannot decrease because of this operation as ( f , c) is optimal. Further, the objective function may not increase: Assume the contrary. Then P 2 contains more edges than P 1 . Let (y ′′ , y) be the last edge of P 2 and ∆ ′ := f s (y ′′ , y). We would obtain a better feasible solution by setting f s (e) := f s (e)-∆ ′ for each edge e ∈ P 2 and f s (e) := f s (e)+∆ ′ for each edge e ∈ P 1 , contradicting the optimality of ( f , c).

The following theorem shows that model (LSP) and the SHORTCUT PROBLEM are equivalent with regard to exact solutions. Theorem 4. Given an optimal solution E ′ of the SHORTCUT PROBLEM, the assignment

c ′ (u, v) := 1 , (u, v) ∈ E ′ 0 , otherwise
can be extended to an optimal solution of (LSP). Further, given an optimal solution ( f , c) of (LSP), the set

E ′′ := {(u, v) ∈ V ×V | c(u, v) = 1}
is an optimal solution for the SHORTCUT PROBLEM.

Proof. Let (G = (V, E, len), c) be a SHORTCUT PROBLEM-instance. As we have observed before, maximizing the gain is equivalent to finding a shortcut assignment

E ′ that minimizes obj(E ′ ) := ∑ s,t∈V h G[E ′ ] (s,t).
Throughout this proof, we use this point of view. Let E ′ be a shortcut assignment of (G = (V, E, len), c). Consider an arbitrary vertex s ∈ V . There is a shortest-paths tree T s ⊆ G[E ′ ] such that, for each t ∈ V with dist(s,t) < ∞, the number of edges on the s-t-path in T s equals h G[E ′ ] (s,t). Such a tree T s can be computed using Dijkstra's algorithm by altering the distance labels to be tuples (edge length, hop distance) and applying lexicographical ordering. Let

c ′ (u, v) = 1 , (u, v) ∈ E ′ 0 , otherwise and
f ′s (u, v) = 0 , (u, v) ∈ T s |{w | w is descendant of v in T s }| , otherwise
The pair (c ′ , f ′ ) is a feasible solution of (LSP). We denote by P T s (s,t) the s-t-path in T s and by |P T s (s,t)| the number of edges on this path. It is

∑ t∈P s h G[E ′ ] (s,t) = ∑ t∈P s |P T s (s,t)| = ∑ t∈P s ∑ e∈T s 1 e (P T s (s,t)) = ∑ e∈T s ∑ t∈P s 1 e (P T s (s,t)) = ∑ (u,v)∈T s |{w | w is descendant of v in T s }| = ∑ u∈P s , v∈P + (s,u), u =v f ′s (u, v) Consequently, obj( f ′ , c ′ ) = obj(E ′ ).
On the other hand, let ( f , c) be a feasible solution of (LSP). With Lemma 3 we may assume that, for each node s, the subgraph induced by

T s := {(u, v) ∈ V × V | f s (u, v) > 0} is a tree. Hence, we can show by induction that f s (u, v) = |{w | w is descendant of v in T s }| for each edge (u, v) ∈ T s . Further, the set E ′′ = {(u, v) ∈ V ×V | c(u, v) = 1}
is a feasible solution of the SHORTCUT PROBLEM. Finally, we show that obj(E ′′ ) ≤ obj( f , c). We consider each root s ∈ V separately. To bound the hop-distances in G[E ′′ ] starting at s from above we use the shortest-paths tree T s as a witness. This yields

∑ t∈P s h G[E ′′ ] (s,t) ≤ ∑ t∈P s |P T s (s,t)|
With the same computation as above, we derive

∑ t∈P s h G[E ′′ ] (s,t) ≤ ∑ t∈P s |P T s (s,t)| = ∑ u∈P s , v∈P + (s,u), u =v f s (u, v)
which shows the claim.

Tuning the Flow-Based Formulation. In order to simplify model (LSP), we relax Constraint 15 to

f s (u, v) ∈ R ≥0 (s, u, v) ∈ B ( 17
)
and denote the resulting model [START_REF] Brunel | Space-Efficient SHARC-Routing[END_REF][START_REF] Delling | Engineering and Augmenting Route Planning Algorithms[END_REF][START_REF] Demetrescu | Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07)[END_REF][START_REF] Geisberger | Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks[END_REF][START_REF] Goldberg | Reach for A*: Efficient Point-to-Point Shortest Path Algorithms[END_REF][START_REF] Goldberg | Reach for A*: Shortest Path Algorithms with Preprocessing[END_REF][START_REF] Gutman | Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks[END_REF] by (RLSP).

Lemma 4. Let ( f , c) be a solution of (RLSP). Then there is a solution ( f ′ , c) of (LSP) with same objective value.

Proof. Note that Lemma 3 also holds for (RLSP). Hence, we assume that, for each node s, the subgraph induced by

T s := {(u, v) ∈ V ×V | f s (u, v) >
0} is a tree. The integrality of f now follows by induction on the nodes in reverse topological order and Constraint 12.

In order to heuristically speedup the solving process we may add the following constraints that give bounds on the f -variables.

f s (u, v) ≤ |P + (s, v)| (s, u, v) ∈ B ( 18
)
An additional heuristic improvement works as follows:

∑ (s,u,v)∈B f s (u, v) =obj( f ,c) ≥ ∑ s,t∈V h G (s,t) lower bound of obj( f , 0) -∑ a,b∈V dist(a,b)<∞ c(a, b) • (h G (a, b) -1) • |P(a, b)| upper bound of improvement because of shortcut (a, b) (19)
to additionally tighten the model.

Case Study. While our main interest on the problem is of theoretical nature, we report some experimental results of the ILP-based approaches. This shall allow for a brief comparison of both formulations and for assessing the heuristic improvements. Our implementation is written in Java using CPLEX 11.2 as ILP-Solver and was compiled with Java 1.6. The tests were executed on one core of an AMD Opteron 6172 Processor, running SUSE Linux 10.3. The machine is clocked at 2.1 GHz and has 16 GB of RAM per processor. We tested on four different graphs. The graph G disk is a unit-disk graph and generated by randomly assigning 100 nodes to a point in the unit square of the Euclidean plane. Two nodes are connected by an edge if their Euclidean distance is below a given radius. This radius is adjusted such that the resulting graph has approximately 1000 edges. The graph G ka represents a part of the road network of Karlsruhe. It contains 102 nodes and 241 edges. The graph G grid is based on a two-dimensional 10 × 10 square grid. The nodes of the graph correspond to the crossings in the grid. There is an edge between two nodes if they are neighbors on the grid. Finally, the graph G path is a path consisting of 30 nodes. In each graph, edge weights are randomly chosen integer values between 1 and 1000. For each experiment, the computation time has been limited to 60 minutes. The integrality constraints of the variables k t s (•, •) of the simple model and the variables f s (•, •) of the flow model have been relaxed. Some example outcomes are depicted in Figure 3.

The results are summarized in 18are incorporated in the model. For the simple model, we adapted Equation 19 in a straightforward fashion. Columns opt show if an optimal solution has been found and proven to be optimal. Columns gap give the guaranteed approximation ratio of the best feasible solution found within 60 minutes, i.e., the value (best feasible solution found -best proven lower bound) / best proven lower bound. The value of gap is ∞ if no feasible solution has been found in 60 minutes. Finally, columns time give the computation time in minutes.

We observe that the simple model does not benefit from Equation 19 and the plain version without this enhancement is always superior. For the flow formulation, it turned out that the version enriched with Equation 18is best: This version is always better than the plain model without improvement and than the formulation enhanced only with Equation 19. Further, it is most times better than the version enriched with Equation 19 and 18. Finally, we see that Equation 19 was an improvement to the plain model if more than one shortcut was to be inserted.

Comparing the two formulations we obtain that the flow formulation is superior. The flow formulation enhanced with Equation 18was most times better than the simple model, sometimes with a big gap. With one exception, the difference was small when the simple model was better. Concluding, in this testset the flow formulation enhanced with Equation 18 In our experiments, we did not take memory consumption into account as the limiting factor was computation time. However, to enable a vague comparison of the memory consumption, we report in Table 2 the number of nonzeros reported by CPLEX after the presolve routine. Note that, this number turned out to be almost independent from the number of shortcuts to be inserted.

graph ka with 5 optimal shortcuts graph ka with 10 optimal shortcuts graph grid with 5 optimal shortcuts graph grid with 10 optimal shortcuts graph disk with 5 optimal shortcuts graph disk with 10 optimal shortcuts Fig. 3: Optimal shortcut assignments for some example graphs.

Approximation using the GREEDY-Strategy

In this section, we propose a polynomial-time algorithm that approximatively solves the SHORT-CUT PROBLEM in a greedy fashion. Given the number c of shortcuts to insert, the approach finds a c-approximation of the optimal solution if the underlying graph is sp-unique. While the algorithm works on arbitrary graphs, we restrict our description to strongly connected graphs to improve readability. The restriction to sp-unique graphs is only needed for achieving the approximation guarantee.

Description. Given the instance (G, c), the GREEDY approximation scheme consists of iteratively constructing a sequence G = G 0 , G 1 , . . . , G c of graphs where G i+1 results from solving the SHORT-CUT PROBLEM on G i with only one shortcut allowed to insert. The pseudocode for the approach is given as Algorithm 1. The following theorem shows the approximation ratio for GREEDY.

Algorithm 1: GREEDY(G, c)

input : graph G = (V, E, len), number of shortcuts c output:

shortcut assignment E ′ 1 E ′ ← / 0; for i = 1, 2, . . . , c do 2 (x, y) ← arg max (x,y)∈(V ×V )\(E∪E ′ ), dist(x,y)<∞ {w G[E ′ ] ({(x, y)})} 3 E ′ ← E ′ ∪ {(x, y)} 4 output E ′ .
Theorem 5. Consider an sp-unique graph G = (V, E, len) together with a positive integer c ∈ Z >0 .

The solution E ′ := GREEDY(G, c) of the GREEDY-approach is a c-approximation of an optimal solution E * , i.e., w G (E * )/w G (E ′ ) ≤ c.

Proof. Let e 1 ∈ E ′ be the first shortcut inserted by GREEDY. Then, w G (e) ≤ w G (e 1 ) for each e ∈ E * . Moreover by Lemma 2, w(E * ) ≤ ∑ e∈E * w(e). This yields

w G (E * ) ≤ ∑ e∈E * w G (e) ≤ c ∑ i=1 w G (e 1 ) = c • w G (e 1 ) ≤ c • w G (E ′ ) which shows w(E * )/w(E ′ ) ≤ c.
Basic Runtime Issues. The runtime of GREEDY crucially depends on how the next shortcut to be inserted is found. A straightforward approach would be to first precompute the distance dist(s,t) for each pair s,t ∈ V as well as the shortest-paths subgraph G s for each node s ∈ V . Then, the Greedily finding one optimal shortcut in sp-unique graphs. In sp-unique graphs each shortest path is edge-minimal. Hence, we can compute the gain of a shortcut (a, b) restricted to a pair of nodes (s,t) ∈ P(a, b) by the equation

h G (s,t) -h G[(a,b)] (s,t) = h G (a, b) -1. ( 20
)
Furthermore, for general graphs, the following lemma holds. Proof. ⇒: Let (s,t) ∈ P(a, b), then there is a shortest s-t-path p containing first a and then b.

Obviously, this path also shows that t ∈ P + (s, b) and as subpaths of shortest paths are again shortest paths, the subpath of p from s to b is a witness that s is in

P -(a, b). ⇐: Let s ∈ P -(a, b) and t ∈ P + (s, b). Then, dist(s, b) = dist(s, a)+dist(a, b) and hence dist(s,t) = dist(s, b) + dist(b,t) = dist(s, a) + dist(a, b) + dist(b,

t). This shows that (s,t) ∈ P(a, b).

Exploiting Lemma 5 and Equation 20, we obtain

w(a, b) = (h G (a, b) -1) • |P(a, b)| = (h G (a, b) -1) • ∑ s∈P -(a,b) |P + (s, b)|. ( 21
)
This equation directly leads to Algorithm 2 that finds one optimal shortcut for sp-unique graphs.

The runtime of the algorithm lies in O(|V | 3 ) as the computation of The problem of this approach is that we can not apply Algorithm 2 for the GREEDY-strategy, even when the input graph is sp-unique: After insertion of the first shortcut, the augmented graph is not sp-unique any more and hence we can not use Equation 20.

|P + (s, b)| is linear in |V |: For each v ∈ V we have to check if dist(s, b) + dist(b, v) = dist(s, v). Algorithm 2: GREEDY STEP ON SP-UNIQUE GRAPHS input : graph G = (V, E, len), distance table dist(•, •) of G output: optimal shortcut (a, b) 1 initialize w(•, •) ≡ 0 2 compute h G (•, •) 3 for s ∈ V do
An O(|V | 3 )-implementation for greedily finding one optimal shortcut. In the following, we generalize the above approach to work with arbitrary graphs. The offset

ω sb (t) := h G (s, b) + h G (b,t) -h G (s,t)
reflects the increase of the hop-distance between given nodes s and t, if we restrict ourselves to shortest paths containing b. We define the potential gain g s (a, b) of a shortcut from a to b with respect to s as

g s (a, b) := h G (a, b) -1 -ω sa (b) .
This is an upper bound for the decrease of the hop-distance between s and any t in the graph

G[(a, b)]. Lemma 6. For all vertices s,t, a, b ∈ V such that (s,t) ∈ P(a, b) it holds that h G (s,t) -h G[(a,b)] (s,t) = max{g s (a, b) -ω sb (t), 0}.
Proof. Directly from the definition of potential gain and offset we obtain

g s (a, b) -ω sb (t) > 0 ⇐⇒ h G (s,t) > h G (s, a) + 1 + h G (b,t) (22
)

Case [g s (a, b) -ω sb (t) > 0]. Then h G (s,t) > h G (s, a) + 1 + h G (b,t). The presence of shortcut (a, b) decreases the s-t-hop-distance to h G[(a,b)] (s,t) = h G (s, a) + 1 + h G (b,t)
as the lemma assumes that there is a shortest s-a-b-t-path. This yields

h G (s,t) -h G[(a,b)] (s,t) = h G (s,t) -h G (s, a) -1 -h G (b,t) = h G (a, b) -1 -h G (s, a) -h G (a, b) + h G (s, b) =-ω sa (b) -h G (s, b) -h G (b,t) + h G (s,t) =-ω sb (t) = g s (a, b) -ω sb (t). Case [g s (a, b) -ω sb (t) ≤ 0]. With Equation (22) we obtain h G (s,t) ≤ h G (s, a) + 1 + h G (b,t).
Hence, a shortcut (a, b) does not improve the hop-distance from s to t and we have h

G (s,t) - h G[(a,b)] (s,t) = 0.
Lemma 6 implies that vertices t in P + (s, b) with the same value of ω sb (t) benefit from a shortcut ending at b to the same extent, if we restrict ourselves to shortest paths starting at s. We divide the vertices in P + (s, b) in equivalence classes with respect to ω sb . Let

∆ i (s, b) := |{t ∈ P + (s, b) | ω sb (t) = i}|
be the number of vertices in these equivalence classes.

The algorithm we propose makes use of partial (weighted) sums of the ∆ i (s, b) for fixed s and b in V . For convenience, we introduce two further abbreviations :

C r (s, b) := r ∑ i=0 ∆ i (s, b) D r (s, b) := r ∑ i=0 i • ∆ i (s, b).
With these definitions, we can form an alternative equation for w(a, b). Lemma 7. Let a, b, s,t ∈ V be arbitrary nodes. Then

w(a, b) = ∑ s∈P -(a,b) g s (a,b)>0 g s (a, b) •C g s (a,b)-1 (s, b) -D g s (a,b)-1 (s, b) . Proof. w(a, b) = ∑ s,t∈V h G (s,t) -h G[(a,b)] (s,t) = ∑ (s,t)∈P(a,b) h G (s,t) -h G[(a,b)] (s,t) + ∑ (s,t) / ∈P(a,b) h G (s,t) -h G[(a,b)] (s,t) =0 = ∑ (s,t)∈P(a,b) ω sb (t)<g s (a,b) h G (s,t) -h G[(a,b)] (s,t) + ∑ (s,t)∈P(a,b) ω sb (t)≥g s (a,b) h G (s,t) -h G[(a,b)] (s,t)
=0 with Lemma 6

.

With Lemma 6, we yield

w(a, b) = ∑ (s,t)∈P(a,b) ω sb (t)<g s (a,b) g s (a, b) -ω sb (t).
It is ω sb (t) ≥ 0 as (s,t) ∈ P(a, b), hence with Lemma 5 we have

w(a, b) = ∑ s∈P -(a,b) g s (a,b)>0 g s (a,b)-1 ∑ i=0 ∑ t∈P + (s,b) ω sb (t)=i g s (a, b) -i.
As g s (a, b) is independent of t we can transform the equation as follows

w(a, b) = ∑ s∈P -(a,b) g s (a,b)>0 g s (a,b)-1 ∑ i=0 ∆ i (s, b) • g s (a, b) -i = ∑ s∈P -(a,b) g s (a,b)>0 g s (a, b) g s (a,b)-1 ∑ i=0 ∆ i (s, b) - g s (a,b)-1 ∑ i=0 i • ∆ i (s, b) = ∑ s∈P -(a,b) g s (a,b)>0 g s (a, b) •C g s (a,b)-1 (s, b) -D g s (a,b)-1 (s, b) .
This finishes the proof.

Lemma 7 is the key for obtaining our O(|V | 3 )-algorithm for performing one GREEDY-step, which is stated as Algorithm 3: First, all distances and hop-distances are precomputed. We then consider, for each s ∈ V , each shortest-paths subgraph with root s separately. It is easy to see that the values of ∆

• (s, •), C • (s, •) and D • (s, •) can be computed in time O(|V | 2 ).
Prepared with these values we are ready to apply Lemma 7. We initialize the values w(•, •) with 0. For each triple s, a, b ∈ V , we check if there is a shortest s-a-b-path and if g s (a, b) > 0. We increment w(a, b) according to Lemma 7 in case of a positive answer. Finally, we take an arbitrary shortcut

3: GREEDY STEP Input: Strongly connected graph G = (V, E, len) Output: shortcut (a, b) maximizing w G ({(a, b)}) 1 compute dist(•, •), h(•, •) 2 initialize w(•, •) ≡ 0 3 initialize ∆ i (•, •) ≡ 0 4 for s ∈ V do 5 for b,t ∈ V do /* compute ∆ */ 6 if there exists a shortest s-t-path containing b in G then 7 j ← ω sb (t) 8 ∆ j (s, b) ← ∆ j (s, b) + 1 9 for b ∈ V do /* compute C and D */ 10 C 0 (s, b) ← ∆ 0 (s, b) 11 D 0 (s, b) ← 0 12 for r := 1 to |V | -1 do 13 C r (s, b) ← C r-1 (s, b) + ∆ r (s, b) 14 D r (s, b) ← D r-1 (s, b) + r • ∆ r (s, b)

Approximation via Partitioning

The second algorithm works for sp-unique graphs in which the degree of each vertex is bounded by a constant. Given an sp-unique graph G = (V, E, len) in which the degree of each vertex is bounded by a constant B. Algorithm 4 partitions V into small subsets, solves the SHORTCUT PROBLEM restricted to each subset and then chooses the best solution among all subsets as an approximated solution. If the subsets are small enough, we can solve the SHORTCUT PROBLEM restricted to each set in polynomial time.

In detail, our scheme works as follows. First, we partition the set V into sets P = {P 1 , . . . , P k }, where each P i has size size = c |V | ε /B for an arbitrary constant ε ∈ (0, c). Then, for each set P i ∈ P, we compute the neighborhood C i := P i ∪ {u ∈ N(v) | v ∈ P i } of P i and solve the shortcut problem on G restricted to shortcuts in C i . That is, we compute

S i = argmax{w(S) | S is shortcut assignment ⊆ C i ×C i and |S| ≤ c}.
Finally, we determine the set C i , for which the shortcut assignment yields the highest gain. This solution gives an approximation ratio of

O max |V | 1-ε c , 1 c • |V | 1+ ε c
to the optimal solution (see Theorem 1). The following theorem shows the approximation ratio for PARTITION. A detailed discussion on the ratio is given after the proof.

Theorem 1. Given a weighted, directed, SP-unique graph G = (V, E, len) in which the degree of each vertex is bounded by a constant, and a positive integer c ∈ N. Then, the solution computed by PARTITION is an

O max |V | 1-ε c , 1 c • |V | 1+ ε c
approximation for the optimal solution of the SHORTCUT PROBLEM instance (G, c).

Proof. The proof is outlined as follows: We break up the shortcuts in an optimal shortcut assignment into shortcuts whose endpoints are contained in the same neighborhood. We then show that at least one of the neighborhoods contains a subset of these shortcuts that fulfills the approximation guarantee stated in the theorem.

Let E * denote an optimal solution to (G, c), P the partition and C the set of neighborhoods C i used by PARTITION. Now each shortcut e * = (a, b) ∈ E * is subdivided as follows: Let p = (v 1 , . . . , v r ) be the unique shortest path from a to b in G and D(e * ) be the set of shortcuts containing (v i , v i+2 ) for all odd i with 1 ≤ i ≤ i -2, see Figure 4a. It is easy to see that for each of these shortcuts there is at least one neighborhood containing both endpoints, as these are connected by a path of length 2 in the original graph. Let E ′ = e * ∈E * D(e * ) and E i be the set of e = {a, b} ∈ E ′ such that both a and b are contained in C i . Due to the construction of the E i , this is a cover of E ′ , i. e. We say that two shortcuts (v i 1 , v i 2 ) and (v j 1 , v j 2 ) overlap on a path v 1 , . . . , v r if neither i 2 ≤ j 1 nor j 2 ≤ i 1 , see Figure 4b. The shortcuts in E i that are the result of dividing non-overlapping shortcuts on the shortest s-t-path are pairwise non-overlapping, thus 2

⌈|V |/size⌉ i=1 E i = E ′ . Claim.w G (E * ) ≤ 2 • ∑ ⌈|V |/size⌉ i=1 w G (E i ) Let s,
• ⌈|V |/size⌉ ∑ i=1 |{e ∈ E i | ∃e * ∈ E * (s,t) with e ∈ D(e * )}| ≤ 2 • ⌈|V |/size⌉ ∑ i=1 h G (s,t) -h G[E i ] (s,t) Hence, it is w G (E * ) = ∑ s,t∈V h G (s,t) -h G[E * ] (s,t) ≤ 2 • ∑ s,t∈V ⌈|V |/size⌉ ∑ i=1 h G (s,t) -h G[E i ] (s,t) = 2 • ⌈|V |/size⌉ ∑ i=1 w G (E i )
Let B be the maximum degree of a node in G and S ′ be the solution computed by PARTITION. For each i, two cases may occur:

-if |E i | ≤ c, since S ′ = argmax{w G ( S i ) | i = 1, 2, . . . , ⌈|V |/size⌉}, then w G (E i ) ≤ w G (S ′ ). -If |E i | > c,
G (E i ) ≤ w G (S ′ ) |E i | c ≤ w G (S ′ ) size 2 B 2 c . It follows that, w(S * ) ≤ 2 ⌈|V |/size⌉ ∑ i=1 w(S ′ ) max 1, size 2 • B 2 c ≤ 2 |V | size w(S ′ ) max 1, size 2 • B 2 c
Hence, the approximation ratio can be bound as follows.

w(S * ) w(S ′ ) ≤ 2 |V | size max 1, size 2 • B 2 c = O |V | size max 1, size 2 c = O |V | c |V | ε max 1, c |V | 2ε c = O max |V | 1-ε c , 1 c • |V | 1+ ε c .
Discussion of Approximation Bounds. In this section, we compare PARTITION and GREEDY against each other and against trivial guarantees on some example configurations. Let G = (V, E, len) be a weighted, directed, SP-unique graph in which the degree of each vertex is bounded by a constant. The latter assumption is not necessary for the statements concerning the greedy algorithm, its approximation guarantee of c holds for arbitrary degree distributions. We distinguish examplarily four settings for the parameter c:

c GREEDY PARTITION Trivial bound O(1)
O( 1)

Ω (|V |) Θ (|V | 3 ) Θ (log |V |) Θ (log |V |) Θ (|V |) Θ |V | 3 log |V | Θ (|V |) Θ (|V |) Θ (|V |) Θ (|V | 2 ) Θ (|V | • log |V |) Θ (|V | • log |V |) Θ (|V |) Θ ( |V | 2 log |V | )
Table 3: Comparison of approximation bounds for sample configurations c ∈ O(1): In this case, as stated in Section 3, the problem is polynomially solvable by a bruteforce algorithm. However, the runtime of this approach is exponential in c, while the runtime of the greedy algorithm has only a linear dependence on c and its approximation guarantee is constant. The guarantee given by the partitioning approach is in ω

(|V |). -c ∈ Θ (log(|V |)): Let x > 0 be a constant, then |V | 1-ε x•log(|V |) = |V |•2 -ε x and 1 log(|V |) •|V | 1+ ε x•log |V | = 1 log(|V |) • |V | • 2 ε x .
Hence, the guarantee given for PARTITION is in Θ (|V |), which is worse than the bound of the greedy algorithm.

-c ∈ Θ (|V |): It is |V | ≥ |V | 1-ε x•|V | ≥ |V | 1-ε x•log(|V |)
. Thus, analoguous to the last case, the approximation guarantee of PARTITION is in Θ (|V |), which matches the bound given for GREEDY. A summary of these configurations is given in Table 3.

Evaluation of the Measure Function

To evaluate the gain of a given shortcut assignment, a straightforward algorithm requires computing all-pairs shortest-paths. Since this computation is expensive, we provide a probabilistic method to quickly assess the quality of a shortcut assignment E ′ . This approach can be used for networks where the computation of all-pairs shortest-paths is prohibitive, such as big road networks. For the sake of simplicity we state the approach for the evaluation of µ(E ′ ) := ∑ s,t∈V h G[E ′ ] (s,t), the adaption to the SHORTCUT PROBLEM is straightforward. More concrete, we apply the sampling technique to obtain an unbiased estimate for µ(E ′ ) and apply Hoeffding's Bound [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] to get a confidence intervall for the outcome. As an auxiliary result we propose algorithms that approximate the maximum hop-distance in a graph.

Theorem 6 (Hoeffding's Bound). If X 1 , X 2 , . . . , X K are real valued independent random variables with a i ≤ X i ≤ b i and expected mean µ = E[∑X i /K], then

P ∑ K i=1 X i K -µ ≥ ξ ≤ 2e -2K 2 ξ 2 / ∑ K i=1 (b i -a i ) 2
for each ξ > 0.

We now model the assessment of a shortcut assignment E ′ of a graph G in terms of Hoeffding's Bound. Let X 1 , . . . , X K be the family of random variables such that X i is defined by

X i := |V | ∑ t∈V h G[E ′ ] (s i ,t)
Approximating the Shortest-Paths Diameter. A straightforward approach to compute the exact shortest path diameter requires computing all-pairs shortest-paths. This is reasonable when working with mid-size graphs that allow the computation of all-pairs shortest-paths at least once and for which a large number of shortcut assignments is to be evaluated. In case the computation of all-pairs shortest-paths is prohibitive one can also use upper bounds for the shortest path diameter.

We obtain an upper bound the following way: First we compute an upper bound diam(G) for the diameter of G. To do so we choose a set of nodes s 1 , s 2 , . . . , s l uniformly at random. We denote by ε

G (v) = max{dist G (v,t) | t ∈ V } the eccentricity of node v in graph G = (V, E, len). For each node s i , the value ε← - G (s i ) + ε G (s i ) is an upper bound for the diameter of G: Let u, v ∈ V be such that dist(u, v) = diam(G). Then diam(G) = dist(u, v) ≤ dist(u, s i ) + dist(s i , v) ≤ ε← - G (s i ) + ε G (s i ) .
We set diam(G) to be the minimum of these values over all s i . The bound diam(G) is a 2approximation for the exact diameter diam(G) of G (already for l = 1) as there are u, v ∈ V and

s i ∈ V such that diam(G) = dist(u, s i ) + dist(s i , v) ≤ diam(G) + diam(G) = 2 • diam(G).
Let len max and len min denote the lengths of a longest and a shortest edge in G, respectively. The value diam(G)/ len min is an upper bound for spDiam(G): Let P be an edge-minimal shortest path in G with |P| = spDiam(G) edges. Then

spDiam(G) = |P| ≤ len(P) len min ≤ diam(G) len min ≤ diam(G) len min .
Further, diam(G)/ len min is a 2•len max / len min -approximation for spDiam(G) as with spDiam(G) ≥ diam(G)/ len max follows that diam(G) len min ≤ 2 diam(G) len min ≤ 2 len max • spDiam(G) len min .

A more expensive approach works as follows, pseudocode is given as Algorithm 6: After computing diam(G), we choose a tuning parameter η. Then we grow, for each node s in G, a shortestpaths tree whose construction is stopped directly before one vertex with distance greater than diam(G)/η is settled. When breaking ties between different shortest paths we favor edge-minimal shortest paths. We denote by τ max the maximum number of edges of the shortest paths on any of the trees grown plus one. Then spDiam(G) := τ max • η is an upper bound for the shortest path diameter of G: Let P = (v 1 , . . . , v n ) be an arbitrary edge-minimal shortest path in G. We can split P in sub-paths

τ max • η spDiam(G) ≤ (spDiam(G) + 1)η spDiam(G) = η(1 + 1 spDiam(G) ) ≤ η(1 + 1 τ max -1 ) ≤ 2 • η .
Obviously, the whole proceeding only makes sense for graphs for which the shortest path diameter is much smaller than the number of nodes. This holds for a wide range of real-world graphs, in particular for road networks. For example, the road network of Luxembourg provided by the PTV AG [22] consists of 30733 nodes and has a shortest path diameter of only 429. The road network of the Netherlands consists of 946.632 nodes and has a shortest-paths diameter of 1503.

Conclusion

Summary. In this work we studied two problems. The SHORTCUT PROBLEM is the problem of how to insert c shortcuts in G such that the expected number of edges that are contained in an edge-minimal shortest path from a random node s to a random node t is minimal. The REVERSE SHORTCUT PROBLEM is the variant of the SHORTCUT PROBLEM where one has to insert a minimal number of shortcuts to reach a desired expected number of edges on edge-minimal shortest paths.

We proved that both problems are NP-hard and that there is no polynomial-time constant-factor approximation algorithm for the REVERSE SHORTCUT PROBLEM, unless P = NP. Furthermore, no polynomial-time algorithm exists that approximates the SHORTCUT PROBLEM up to an additive constant unless P = NP.

The algorithmic contribution focused on the SHORTCUT PROBLEM. We proposed two ILPbased approaches to exactly solve the SHORTCUT PROBLEM: A straightforward formulation that incorporates O(|V | 4 ) variables and constraints and a more sophisticated flow-like formulation that requires O(|V | 3 ) variables and constraints.

We considered two approximation strategies. A straightforward greedy approach computes a c-approximation of the optimal solution if the input graph is such that shortest paths are unique.

We further presented a dynamic program that performs a greedy step in time O(|V | 3 ) which yields an overall runtime in O(c • |V | 3 ). The main idea of the second approach is to partition the set of nodes. It computes an

O max |V | 1-ε c , 1 c • |V | 1+ ε c
approximation of the optimal solution if shortest paths in the input graph are unique and the maximum degree is bounded by a constant. If ε is a constant, this algorithm is polynomial.

Finally, we proposed a probabilistic method to quickly evaluate the measure function of the SHORTCUT PROBLEM. This can be used for large input networks where an exact evaluation is prohibitive.

Future Work. A wide range of possible future work exists for the SHORTCUT PROBLEM. From a theoretical point of view the probably most interesting open field is the approximability of the SHORTCUT PROBLEM. It is still unknown if it is in APX. Furthermore, it would be helpful to identify graph classes for which the SHORTCUT PROBLEM or the REVERSE SHORTCUT PROB-LEM becomes tractable. FPT-algorithms are also desirable. From an experimental point of view it would be interesting to develop heuristics that find good shortcuts for large real-world inputs. In particular, evolutionary algorithms and local search algorithms seem promising.

Finally, we pose the question if the given ILP-approaches can be used for the design of approximation algorithms. We do not see good chances for rounding-based methods. However, other techniques like primal-dual arguments might work.

3 Fig. 2 :

 32 Fig. 2: Example Graph G with shortcuts s 1 , s 2 , s 3 . All edges for which no weight is given in the picture have weight 1.

  evaluation of a possible shortcut can be done by running breadth-first searches on the |V | graphs G s . After insertion of a shortcut (a, b) to G, the shortest-paths subgraphs G s can be adapted by adding (a, b) to each subgraph G s for which dist(s, a) + dist(a, b) = dist(s, b). Hence G s contains at most |E| + c edges and the time needed for evaluating one shortcut is O(|V | • (|V | + |E| + c)). This leads to a runtime in O(|V | 2 •|V |•(|V |+|E|+c)) for evaluating all |V | 2 possible shortcuts. The runtime O(|V | 2 log |V | + |V | • |E|) of precomputing the shortest-paths subgraphs can be neglected. In the remainder of this section, we show how to perform this step in time O(|V | 3 ) using a dynamic program. Consequently, the GREEDY-strategy can be implemented to work in time O(c • |V | 3 ).

Lemma 5 .

 5 (s,t) ∈ P(a, b) if and only if s ∈ P -(a, b) and t ∈ P + (s, b).

4 for b ∈ V do 5 compute 6 for a ∈ V do 7 if

 4567 |P + (s, b)| dist(s, a) + dist(a, b) = dist(s, b) then 8 w(a, b) ← w(a, b) + (h G (a, b) -1)|P + (s, b)| 9 output arbitrary (a, b) with maximum w(a, b)

  (a, b) that maximizes w(a, b). The correctness of the algorithm directly follows from the definitions of ∆ • (•, •), C • (•, •) and D • (•, •) and Lemma 7. To reach the runtime in O(|V | 3 ) we answer the question if a shortest s-a-b path exists by checking if dist(s, a) + dist(a, b) = dist(s, b).

Algorithm

  15 for a, b ∈ V do /* apply Lemma 7 */ 16 if there exists a shortest s-b-path containing a and g s (a, b) > 0 then 17 w(a, b) ← w(a, b) + g s (a, b) •C g s (a,b)-1 (s, b) -D g s (a,b)-1 (s, b) 18 output arbitrary (a, b) with maximum w(a, b)

Algorithm 4 :1Fig. 4 :

 44 Fig. 4: Illustrations to proof of Theorem 1

  h G (s,t) -h G[E * ] (s,t) = ∑ e * ∈E * (s,t) (h G (e * ) -1) ≤ 2 • ∑ e * ∈E * (s,t) |D(e * )|For e * ∈ E * (s,t), the sets D(e * ) are disjoint, as the respective shortcuts e * lie on different parts of the chosen s-t-path. Therefore, 2 • ∑ e * ∈E * (s,t) |D(e * )| = 2 • |{e ∈ E ′ | ∃e * ∈ E * (s,t) with e ∈ D(e * )}| ≤ 2 • ⌈|V |/size⌉ ∑ i=1 |{e ∈ E i | ∃e * ∈ E * (s,t) with e ∈ D(e * )}|

  then we can group the shortcuts in S i into sets of size c. Since S ′ = argmax{w G ( S i ) | i = 1, 2, . . . , ⌈|V |/size⌉}, each set of shortcuts of size c gives a decrease in overall hop length on shortest paths that is smaller than w G (S ′ ) and hence w

  c ∈ Θ (|V | • log(|V |)):The guarantee of the partitioning algorithm stays in Θ (|V |), which is better than the guarantee of the greedy algorithm. Note that this guarantee is much tighter than the trivial bound of |V | 2 log(|V |) given in Section 3.

P 1 =

 1 (v 1 , . . . , v k 1 ), P 2 = (v k 1 , . . . , v k 2 ), . . . , P ℓ = (v k ℓ-1 , . . . , v k ℓ ) such that dist(v k i , v k i+1 ) > diam(G)/η and dist(v k i , v k i+1 -1 ) ≤ diam(G)/η .The number ℓ of these subpaths is at most η as ℓ > η would imply that len(P) > diam(G) η (ℓ -1) ≥ diam(G).

Algorithm 6 : 3 s ← choose node uniformly at random 4 grow shortest-paths tree rooted at s 5 grow 8 T

 63458 COMPUTE UPPER BOUND FOR SHORTEST-PATHS DIAMETERinput : graph G = (V, E, len), tuning parameter l, tuning parameter η output: upper bound spDiam(G) for the shortest-paths diameter of G 1 diam(G) ← ∞; τ ← 0;2 for i = 1, . . . , l do /* compute diam(G) */ shortest-paths tree rooted at s on the reverse graph← -G 6 diam(G) ← min{diam(G), max v∈V {dist(s, v)} + max v∈V {dist(v, s)}} 7 for s ∈ V do/* compute spDiam(G) */ ← grow partial shortest-paths tree rooted at s (favoring edge-minimal shortest paths). Stop growing the tree directly before the first node with dist(s, v) > diam(G)/η is settled. τ max ← max{τ max , 1 + maximal number of edges of a path in T }9 output spDiam(G) := τ max • η It is |P i | ≤ τ max which yields |P| ≤ τ max • η.As P was arbitrary we have that spDiam(G) ≤ τ max • η. Further τ max • η is a 2η-approximation and an η(1 + 1/(τ max -1))-approximation of spDiam(G) : With τ max -1 ≤ spDiam(G) follows that

Table 1 .

 1 Columns mean the following: Columns Eq19 and Eq18 indicate if Equation 19 and Equation

Table 1 :

 1 performed best. Experimental results of the ILP-approaches.

		G grid		G ka		G path		G disk
	shortcuts model Eq19 Eq18 opt gap time opt gap time opt gap time opt gap time
	1 flow	0	2	0	5	0	1	0	2
	1 flow	0	2	0	3	0	0	0	1
	1 flow	0	4	0	8	0	0	0	3
	1 flow	0	2	0	7	0	0	0	2
	1 simple	0 16	0 29	0	1	0 14
	1 simple	0 18	0 49	0	1	0 24
	2 flow	0.02 60	0.09 60	0.2 60	0 12
	2 flow	0 10	0 35	0	8	0	2
	2 flow	0 17	0.01 60	0.06 60	0	2
	2 flow	0	3	0 40	0	9	0	2
	2 simple	0 20	0 26	0	2	0 12
	2 simple	0 21	0 48	0	2	0 20
	5 flow	0.16 60	0.53 60	0.4 60	0.06 60
	5 flow	0 28	0 46	0.16 60	0	4
	5 flow	0.05 60	0.12 60	0.39 60	0 55
	5 flow	0 60	0.01 60	0.17 60	0	9
	5 simple	0 30	0 40	0.04 60	0 15
	5 simple	0 58	∞ 60	∞ 60	0 38
	10 flow	0.58 60	0.83 60	0.45 60	0.11 60
	10 flow	0.03 60	0.49 60	0.27 60	0 27
	10 flow	0.14 60	0.49 60	0.49 60	0.07 60
	10 flow	0.05 60	0.34 60	0.32 60	0 25
	10 simple	∞ 60	∞ 60	0.47 60	0 22
	10 simple	∞ 60	∞ 60	2.08 60	0 39

Table 2 :

 2 Number of nonzeros reported by CPLEX after the presolve routine for each model and graph.

	model Eq19 Eq18	G grid	G ka	G path	G disk
	flow	274.818	328.102	34.391	249.564
	flow	327.022	392.422	41.849	295.460
	flow	342.689	409.157	43.029	311.547
	flow	394.737	473.390	50.379	357.146
	simple	1.241.560 1.724.034 259.211 1.005.390
	simple	1.551.052 2.165.022 324.256 1.250.583

  t be a pair of vertices such that h G (s,t) > h G[E * ] (s,t) and E * (s,t) be the set of shortcuts on an arbitrary hop-minimal shortest s-t-path in G[E * ]. As shortest paths in G are unique, h G (s,t)h G[E * ] (s,t) equals the sum of the hop-distances between the endpoints of the shortcuts in E * (s,t) minus |E * (s,t)|. Furthermore, for each e * in E * , h G (e * ) -1 ≤ 2 • |D(e * )| and thus,

where s i ∈ V is a vertex chosen uniformly at random. We estimate µ(E ′ ) by

we can apply Hoeffding's Bound if we know lower and upper bounds for the variables X i . The values 0 and |V | 3 are trivial such bounds. We introduce the notion of shortest-paths diameter to obtain stronger upper bounds.

Definition. The shortest path diameter spDiam(G) of a graph G is the maximum hop-distance from any node to any other node in G.

Applying Hoeffding's Bound with 0

and with l rel := ξ / μ we have

where the parameter l rel states the relative size of the confidence intervall. The values of the variables X i are chosen by randomly choosing values from the finite population c 1 , . . . , c |V | with replacement where

In [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] it is reported that Hoeffding's Bound stays correct if, when sampling from a finite population, the samples are being chosen without replacement. Algorithm 5 is an approximation algorithm that exploits the above inequality and that samples without replacement.

size of confidence intervall l rel , significance level α output: approximation μ for µ = ∑ s,t∈V h G (s,t)

T ← grow shortest-paths tree rooted at v i (favor edge-minimal shortest paths)