Keywords and Synonyms

Geometric graphs; Euclidean graphs          

Problem Definition

The following classical optimization problem is considered: for a given undirected weighted geometric network, find its minimum-cost sub-network that satisfies a priori given multi-connectivity requirements.

Notations

Let \( { G = (V,E) } \) be a  geometric network, whose vertex set V corresponds to a set of n points in ℝ d for certain integer d, \( { d \ge 2 } \), and whose edge set E corresponds to a set of straight-line segments connecting pairs of points in V. G is called complete if E connects all pairs of points in V.

The cost \( { \delta(x,y) } \) of an edge connecting a pair of points \( { x, y \in \mathbb{R}^d } \) is equal to the Euclidean distance between points x and y, that is, \( { \delta(x,y) = \sqrt{\sum_{i=1}^d (x_i - y_i)^2} } \), where \( { x = (x_1, \dots, x_d) } \) and \( { y = (y_1, \dots, y_d) } \). More generally, the cost \( { \delta(x,y) } \) could be defined using other norms, such as \( { \ell_p } \) norms for any \( { p > 1 } \), i. e., \( { \delta(x,y) = \left(\sum_{i=1}^p (x_i - y_i)^p\right)^{1/p} } \). The cost of the network is equal to the sum of the costs of the edges of the network, \( { \text{cost}(G) = \sum_{(x,y) \in E}\delta(x,y) } \).

A network \( G = (V,E) \) is spanning a set S of points if \( V = S \). \( G = (V,E) \) is k-vertex-connected if for any set \( U \subseteq V \) of fewer than k vertices, the network \( (V\setminus U,\ E\cap ((V\setminus U)\times (V\setminus U)) \) is connected. Similarly, G is k-edge-connected if for any set \( \mathcal{E} \subseteq E \) of fewer than k edges, the network \( (V, E\setminus \mathcal{E}) \) is connected.

The (Euclidean) Minimum-Cost k-Vertex Connected Spanning Network Problem

For a given set S of n points in the Euclidean space ℝd, find a minimum-cost k-vertex connected Euclidean network spanning points in S.

The (Euclidean) Minimum-Cost k-Edge Connected Spanning Network Problem

For a given set S of n points in the Euclidean space ℝd, find a minimum-cost k-edge connected Euclidean network spanning points in S.

A variant that allows parallel edges is also considered:

The (Euclidean) Minimum-Cost k-Edge Connected Spanning Multi-Network Problem

For a given set S of n points in the Euclidean space ℝd, find a minimum-cost k-edge connected Euclidean multi-network spanning points in S (where the multi-network can have parallel edges).

The concept of minimum-cost k-connectivity naturally extends to include that of Euclidean Steiner k-connectivity by allowing the use of additional vertices, called Steiner points. For a given set S of points in ℝd, a geometric network G is a Steiner k-vertex connected (or, Steiner k-edge connected) for S if the vertex set of G is a superset of S and for every pair of points from S there are k internally vertex-disjoint (edge-disjoint, respectively) paths connecting them in G.

The (Euclidean) Minimum-Cost Steiner k-Vertex/Edge Connectivity Problem

Find a minimum-cost network on a superset of S that is Steiner k-vertex/edge connected for S.

Note that for \( { k = 1 } \), it is simply the Steiner minimal tree problem, which has been very extensively studied in the literature (see, e. g., [14]).

In a more general formulation of multi-connectivity graph problems, non-uniform connectivity constraints have to be satisfied.

The Survivable Network Design Problem

For a given set S of points in ℝd and a connectivity requirement function \( { r: S \times S \rightarrow \mathbb{N} } \), find a minimum-cost geometric network spanning points in S such that for any pair of vertices \( { p, q \in S } \) the sub-network has \( { r_{p,q} } \) internally vertex-disjoint (or edge-disjoint, respectively) paths between p and q.

In many applications of this problem, often regarded as the most interesting ones [9,13], the connectivity requirement function is specified with the help of a one-argument function which assigns to each vertex p its connectivity type \( { r_v \in \mathbb{N} } \). Then, for any pair of vertices \( { p, q \in S } \), the connectivity requirement \( { r_{p,q} } \) is simply given as \( { \min\{r_p, r_q\} } \) [12,13,17,18]. This includes the Steiner tree problem (see, e. g., [2]), in which \( { r_p \in \{ 0, 1 \} } \) for any vertex \( { p \in S } \).

A polynomial‐time approximation scheme (PTAS) is a family of algorithms \( { \{\mathcal{A}_{\varepsilon}\} } \) such that, for each fixed \( { \varepsilon > 0 } \), \( { \mathcal{A}_{\varepsilon} } \) runs in time polynomial in the size of the input and produces a \( { (1+\varepsilon) } \)-approximation.

Related Work

For a very extensive presentation of results concerning problems of finding minimum-cost k-vertex- and k-edge-connected spanning subgraphs, non-uniform connectivity, connectivity augmentation problems, and geometric problems, see [1,3,11,15].

Despite the practical relevance of the multi-connectivity problems for geometrical networks and the vast amount of practical heuristic results reported (see, e. g., [12,13,17,18]), very little theoretical research had been done towards developing efficient approximation algorithms for these problems until a few years ago. This contrasts with the very rich and successful theoretical investigations of the corresponding problems in general metric spaces and for general weighted graphs. And so, until 1998, even for the simplest and most fundamental multi-connectivity problem, that of finding a minimum-cost 2-vertex connected network spanning a given set of points in the Euclidean plane, obtaining approximations achieving better than a \( { \frac32 } \) ratio had been elusive (the ratio \( { \frac32 } \) is the best polynomial‐time approximation ratio known for general networks whose weights satisfy the triangle inequality [8]; for other results, see e. g., [4,15]).

Key Results

The first result is an extension of the well-known \( { \mathcal{NP} } \)-hardness result of minimum-cost 2-connectivity in general graphs (see, e. g., [10]) to geometric networks.

Theorem 1

The problem of finding a minimum-cost 2-vertex/edge connected geometric network spanning a set of n points in the plane is \( { \mathcal{NP} } \)-hard.

Next result shows that if one considers the minimum-cost multi-connectivity problems in an enough high dimension, the problems become APX-hard.

Theorem 2 ([6])

There exists a constant \( { \xi > 0 } \) such that it is \( { \mathcal{NP} } \)-hard to approximate within \( { 1 + \xi } \) the minimum-cost 2-connected geometric network spanning a set of n points in \( { \mathbb{R}^{\lceil\log_2 n\rceil} } \).

This result extends also to any \( { \ell_p } \) norm.

Theorem 3 ([6])

For and integer \( { d \ge \log n } \) and for any fixed \( { p \ge 1 } \) there exists a constant \( { \xi > 0 } \) such that it is \( { \mathcal{NP} } \)-hard to approximate within \( { 1 + \xi } \) the minimum-cost 2-connected network spanning a set of n points in the \( { \ell_p } \) metric in ℝd.

Since the minimum-cost multi-connectivity problems are hard, the research turned into the study of approximation algorithms. By combining some of the ideas developed for the polynomial‐time approximation algorithms for TSP due to Arora [2] (see also [16]) together with several new ideas developed specifically for the multi-connectivity problems in geometric networks, Czumaj and Lingas obtained the following results.

Theorem 4 ([5,6])

Let k and d be any integers, \( { k, d \ge 2 } \), and let ε be any positive real. Let S be a set of n points in ℝd. There is a randomized algorithm that in time \( n \cdot (\log n)^{(k d / \varepsilon)^{\mathcal{O}(d)}} \cdot 2^{2^{(k d / \varepsilon)^{\mathcal{O}(d)}}} \) with probability at least 0.99 finds a k-vertex-connected (or k-edge-connected) spanning network for S whose cost is at most \( { (1 + \varepsilon) } \)-time optimal.

Furthermore, this algorithm can be derandomized in polynomial‐time to return a k-vertex-connected (or k-edge-connected) spanning network for S whose cost is at most \( { (1 + \varepsilon) } \) times the optimum.

Observe that when all d, k, and ε are constant, then the running-times are \( { n \cdot \log^{\mathcal{O}(1)}n } \).

The results in Theorem 4 give a PTAS for small values of k and d.

Theorem 5 (PTAS for vertex/edge-connectivity [6,5])

Let \( { d \ge 2 } \) be any constant integer. There is a certain positive constant \( { c < 1 } \) such that for all k such that \( { k \le (\log\log n)^c } \), the problems of finding a minimum-cost k-vertex-connected spanning network and a k-edge-connected spanning network for a set of points in ℝd admit PTAS.

The next theorem deals with multi-networks where feasible solutions are allowed to use parallel edges.

Theorem 6 ([5])

Let k and d be any integers, \( { k, d \ge 2 } \), and let ε be any positive real. Let S be a set of n points in ℝd. There is a randomized algorithm that in time \( n \cdot \log n \cdot (d/\varepsilon)^{\mathcal{O}(d)} + n \cdot 2^{2^{(k^{\mathcal{O}(1)} \cdot (d/\varepsilon)^{\mathcal{O}(d^2)})}} \), with probability at least 0.99 finds a k-edge-connected spanning multi-network for S whose cost is at most \( { (1 + \varepsilon) } \) times the optimum. The algorithm can be derandomized in polynomial‐time.

Combining this theorem with the fact that parallel edges can be eliminated in case \( { k=2 } \), one obtains the following result for 2-connectivity in networks.

Theorem 7 (Approximation schemes for 2-connected graphs, [5])

Let d be any integer, \( { d \ge 2 } \), and let ε be any positive real. Let S be a set of n points in ℝd. There is a randomized algorithm that in time \( n \cdot \log n \cdot (d/\varepsilon)^{\mathcal{O}(d)} + n \cdot 2^{(d/\varepsilon)^{\mathcal{O}(d^2)}} \), with probability at least 0.99 finds a 2-vertex-connected (or 2-edge-connected) spanning network for S whose cost is at most \( { (1 + \varepsilon) } \) times the optimum. This algorithm can be derandomized in polynomial‐time.

For constant d the running time of the randomized algorithms is \( { n \log n \cdot (1/\varepsilon)^{\mathcal{O}(1)} + 2^{(1/\varepsilon)^{\mathcal{O}(1)}} } \).

Theorem 8 ([7])

Let d be any integer, \( { d \ge 2 } \), and let ε be any positive real. Let S be a set of n points in ℝd. There is a randomized algorithm that in time \( n \cdot \log n \cdot (d/\varepsilon)^{\mathcal{O}(d)} + n \cdot 2^{(d/\varepsilon)^{\mathcal{O}(d^2)}} + n \cdot 2^{2^{d^{d^{\mathcal{O}(1)}}}} \), with probability at least 0.99 finds a Steiner 2-vertex-connected (or 2-edge-connected) spanning network for S whose cost is at most \( { (1 + \varepsilon) } \) times the optimum. This algorithm can be derandomized in polynomial‐time.

Theorem 9 ([7])

Let d be any integer, \( { d \ge 2 } \), and let ε be any positive real. Let S be a set of n points in ℝd. There is a randomized algorithm that in time \( n \cdot \log n \cdot (d/\varepsilon)^{\mathcal{O}(d)} + n \cdot 2^{(d/\varepsilon)^{\mathcal{O}(d^2)}} + n \cdot 2^{2^{d^{d^{\mathcal{O}(1)}}}} \), with probability at least 0.99 gives a \( { (1+\varepsilon) } \)-approximation for the geometric network survivability problem with \( { r_v \in \{ 0, 1, 2 \} } \) for any \( { v \in V } \). This algorithm can be derandomized in polynomial‐time.

Applications

Multi-connectivity problems are central in algorithmic graph theory and have numerous applications in computer science and operation research, see, e. g., [1,13,11,18]. They also play very important role in the design of networks that arise in practical situations, see, e. g., [1,13]. Typical application areas include telecommunication, computer and road networks. Low degree connectivity problems for geometrical networks in the plane can often closely approximate such practical connectivity problems (see, e. g., the discussion in [13,17,18]). The survivable network design problem in geometric networks also arises in many applications, e. g., in telecommunication, communication network design, VLSI design, etc. [12,13,17,18].

Open Problems

The results discussed above lead to efficient algorithms only for small connectivity requirements k; the running-time is polynomial only for the value of k up to \( { (\log\log n)^c } \) for certain positive constant \( { c < 1 } \). It is an interesting open problem if one can obtain polynomial‐time approximation schemes algorithms also for large values of k.

It is also an interesting open problem if the multi-connectivity problems in geometric networks can have practically fast approximation schemes.

Cross References

Euclidean Traveling Salesperson Problem

Minimum Geometric Spanning Trees