J Comb Optim DOI 10.1007/s10878-015-9934-2

Efficient approximation algorithms for computing k disjoint constrained shortest paths Longkun Guo1

© Springer Science+Business Media New York 2015

Abstract Let G = (V, E) be a given directed graph in which every edge e is associated with two nonnegative costs: a weight w(e) and a length l(e). For a pair of specified distinct vertices s, t ∈ V , the k-(edge) disjoint constrained shortest path (kCSP) problem is to compute k (edge) disjoint paths between s and t, such that the total length of the paths is minimized and the weight is bounded by a given weight budget W ∈ R+ 0 . The problem is known to be N P-hard, even when k = 1 (Garey and Johnson in  1979). Approximation algorithms with  and intractability,  Computers 2(log r + 1) 1 (1 + ) and (1 + r1 , 1 + r ) have been bifactor ratio 1 + r , r 1 + r developed for k = 2 in Orda and Sprintson (IEEE INFOCOM, pp. 727–738, 2004) and Chao and Hong (IEICE Trans Inf Syst 90(2):465–472, 2007), respectively. For general k, an approximation algorithm with ratio (1, O(ln n)) has been developed for a weaker version of kCSP, the k bi-constraint path problem which is to compute k disjoint st-paths satisfying a given length constraint and a weight constraint simultaneously (Guo et al. in COCOON, pp. 325–336, 2013). This paper first gives an approximation algorithm with bifactor ratio (2, 2) for kCSP using the LP-rounding technique. The algorithm is then improved by adopting a more sophisticated method to round edges. It is shown that for any solution output by the improved algorithm, there exists a real number 0 ≤ α ≤ 2 such that the weight and the length of the solution are bounded by α times and 2 − α times of that of an optimum solution, respectively. The key observation of the ratio proof is to show that the fractional edges, in a basic solution against the proposed linear relaxation of kCSP, exactly compose a graph in which the degree of every vertex is exactly two. At last, by a novel enhancement of

B 1

Longkun Guo [email protected] College of Mathematics and Computer Science, Fuzhou University, Fuzhou, China

123

J Comb Optim

the technique in Guo et al. (COCOON, pp. 325–336, 2013), the approximation ratio is further improved to (1, ln n). Keywords LP rounding · Flow theory · k-Disjoint constrained shortest path · Bifactor approximation algorithm · Cycle cancellation

1 Introduction The paper investigates the k-(edge) disjoint constrained shortest path problem (kCSP), as known as the k restricted shortest path problem, which generalizes the well-known k-(edge) disjoint shortest path problem by considering both length and weight of an edge. The definition of kCSP is formally as in the following: Definition 1 (The k-disjoint constrained shortest path problem, kCSP) For a graph G = (V, E) with a pair of distinct vertices s, t ∈ V , a length function l : E → R+ 0, + , and a weight constraint W ∈ R , the k disjoint a weight function w : E → R+ 0 0 constrained shortest path problem  is to compute k st-paths P1 , . . . , Pk in G, such  that i=1,...,k l(Pi ) is minimized, i=1,...,k w(Pi ) ≤ W and E(P j ) ∩ E(Pl ) = ∅ holds for any j = l. The kCSP problem has broad applications in industry, e.g., end-to-end video transmission with weight constraints, construction of time-sensitive survivable networks with minimum cost, design of minimum cost fault tolerance systems subjected to a given energy consumption constraint (or other additive constraints), etc. Before the technique paragraphs, we would like to give the statement of the bifactor approximation algorithms for the kCSP problem first: An algorithm A is a bifactor (α, β)-approximation for the kCSP problem iff for every instance of kCSP, A computes k disjoint st-paths whose total weight and length are bounded by α·W and β ·l(O P T ) respectively, where  O P T is an optimum solution to the kCSP problem and l(O P T ) = e∈O P T l(e). We shall use bifactor (1, β)-approximation and β-approximation interchangeably in the text while no confusion arises. 1.1 Related work The kCSP problem has been studied for some fixed positive integral k. When k = 1, the problem becomes the constrained shortest path problem of finding a single shortest path that satisfies a given QoS constraint. The problem is known as one of Karp’s 21 N P-hard problems (Garey and Johnson 1979) and admits fully polynomial time approximation scheme (FPTAS) (Lorenz and Raz 2001). As a generalization of the constrained shortest path problem, the single multiple constraint path (MCP) problem of computing a path subjected to multiple given QoS constraints is still attracting interest in the research community. For MCP, the (1 + )-approximation developed by Xue et al. (2008) and Misra et al. (2009) is the best result in thecurrent state  of the art. When k = 2, approximation algorithms with bifactor ratio 1 + r1 , r 1 +     2(log r + 1) 2(log r + 1) 1 (1 + )) and 1 + have been developed for kCSP in , r 1 + r r r

123

J Comb Optim

Orda and Sprintson (2004) and Chao and Hong (2007), respectively. To the best of our knowledge, there exists no non-trivial approximation which strictly obeys the weight constraint in the literature. However, for general k, an approximation algorithm with bifactor ratio (1, O(ln n)) has been developed for the k bi-constraint path problem, a weaker version of the kCSP problem, in which the goal is to compute k disjoint paths satisfying a given length constraint and a given weight constraint simultaneously (Guo et al. 2013). There are also some other interesting results that address other special cases of kCSP. When all edges are with weight 0, this problem becomes the min-sum problem of computing k disjoint paths with the total length minimized, which is known polynomial solvable (Suurballe 1974; Suurballe and Tarjan 1984). The min-min and min-max problems are closely related to the min-sum problem. Both of the two problems are to compute two disjoint paths. The difference is that, the min-min problem is to minimize the length of the shorter path while the min-max problem is to minimize the length of the longer one. Our previous work (Guo and Shen 2013), together with Xu et al.’s (2006) and Bhatia et al.’s (2006), shows that the min-min problem is N P-complete and doesn’t admit K -approximation for any K ≥ 1. Moreover, the edge-disjoint minmin problem remains N P-complete and admits no polynomial time approximation scheme in planar digraphs (Guo and Shen 2012). The min-max problem is also N Pcomplete. But unlike the min-min problem, it admits a best possible approximation ratio two in digraphs (Li et al. 1989), which can be achieved immediately by employing Suurballe and Tarjan’s algorithm for the min-sum problem (Suurballe 1974; Suurballe and Tarjan 1984). In addition, as a variant of the min-max problem, the length bounded disjoint path problem of computing two disjoint paths with lengths both bounded by a given constraint, is also known N P-complete (Li et al. 1989).

1.2 Our technique and results In this paper, we first give an LP relaxation for the kCSP problem. Then by rounding the value of fractional edges of a solution to the LP formula, two approximation algorithms are developed. The first algorithm uses a traditional rounding method, resulting in solutions with a bifactor ratio of (2, 2). The second algorithm improves the ratio of the first approximation to a pseudo ratio of (α, 2 − α) for 0 ≤ α ≤ 2. A pseudo ratio (α, 2 − α) is different to a traditional ratio, which means for any solution output by the approximation algorithm, there always exists 0 ≤ α ≤ 2, such that the weight and length of the solution are bounded by α times and 2 − α times of that of an optimum solution, respectively. Since α could differ for different instances, the ratio is actually (2, 2). However, by extending the technique in Guo et al. (2013), the latter approximation ratio can be further improved to (1, ln n). To the best of our knowledge, this is the first explicit approximation algorithm with a polylogarithmic ratio for the kCSP problem. In addition, as we shall analyze later, the technique in Guo et al. (2013) can be extended to kCSP in a simpler way, resulting in the same ratio but with a much higher time complexity. Like other rounding algorithms, the tricky task, as the major result of this paper, is to show that the round-up solutions are feasible for kCSP. The basic idea is to show

123

J Comb Optim

that the fractional edges of a basic solution to the proposed LP relaxation will compose a graph, in which the degree of every vertex is exactly two. Based on this observation, we show that the round-up edges in the first algorithm could collectively k-connect s and t. The correctness proof of the second algorithm follows a similar line, but acquires a more sophisticated ratio proof due to its complicated rounding method. The following paragraphs are organized as follows: Section 2 gives the LP-rounding algorithm and shows that the resulted solution is with a bifactor ratio(2, 2) and Sect. 3 gives the proof of the correctness of the algorithm; the ratio (2, 2) is improved to a pseudo ratio (α, 2 − α) for 0 ≤ α ≤ 2 in Sect. 4, and then to (1, ln n) in Sect. 5; Sect. 6 concludes this paper.

2 A (2, 2)-approximation algorithm for the kCSP problem The linear programming (LP) relaxation for kCSP is formally as in the following:  (1) min l(e) · xe subject to  e∈δ + (v)





xe −

e∈δ − (v)

 k for v = s xe = 0 for v ∈ V \ {s, t}

xe · w(e) ≤ W

(2) (3)

e∈E

∀e ∈ E(G) :

0 ≤ xe ≤ 1

(4)

where δ + (v) and δ − (v) denote the set of edges leaving and entering v in G, respectively. Before the technique paragraphs, we would like to do some discussion on the above LP formula first. If xe ∈ {0, 1}, the above is exactly the integral linear programming (ILP) formula for the kCSP problem. Moreover, with the relaxation over xe (i.e. use 0 ≤ xe ≤ 1 instead of xe ∈ {0, 1}), a basic solution to the LP formula would remain integral (i.e. xe remains integral for each e) when the weight constraint (i.e. Inequality (3)) is removed. That is, in this case any basic optimum solution to LP (1) would be exactly a set of st-paths with minimum length. That is because LP (1) is totally unimodular without Inequality (3), and hence any basic optimum solution to LP (1) must be integral (Ahuja et al. 1993; Schrijver 1998). But with the weight constraint, LP (1) is no longer totally unimodular, and hence a basic optimum solution to LP (1) is no longer integral even when k = 1 (as depicted in Fig. 1). As the first result of this paper, we show that a basic optimum solution to LP (1) still has an interesting property as stated below: Lemma 2 The set of edges with xe ≥ 21 in a basic optimum solution to LP (1) collectively provide k-connectivity between s and t. Since Lemma 2 is one of our major results and its proof is the most tricky part of this paper, the proof will be deferred to the next section. Based on this lemma, the key idea

123

J Comb Optim Fig. 1 {xe = 21 |e ∈ E(G) \ {e(s, z), e(z, t)}} is a basic optimum solution to LP (1) wrt the given graph G and k = 1. {xe = 13 |e ∈ E(G)}is an optimum solution to LP (7) over this instance, but not a basic optimum solution. Note that neither of the two solutions is integral

Algorithm 1 An LP-rounding algorithm for the kCSP problem. Input: Graph G, distinct vertices s and t, a weight bound W ∈ R+ 0 , a length function l(e) and a weight function w(e); Output: k disjoint st-paths. 1. E S O L ← ∅; 2. Solve LP (1) and get a basic optimum solution χ (Schrijver 1998); 3. For each xe in χ do If xe ≥ 21 then Round xe to 1 and set E S O L ← {e} ∪ E S O L ; /* According to Lemma 2, s would be k-connected to t in E S O L after Step 3.*/ 4. For each e in E S O L do if s is k connected to t in E S O L \ e then E S O L ← E S O L \ {e}; /* Remove redundant edges of E S O L , such that E S O L exactly compose k-disjoint paths. */ 5. Return E S O L as the k-disjoint paths.

of our algorithm is as below: compute a basic optimum solution to LP (1), and round xe to 1 for every edge e with xe ≥ 21 in the solution. Then the algorithm outputs a set of edges with xe = 1 as a solution to the kCSP problem. The detailed algorithm is formally as in Algorithm 1. Step 2 of Algorithm 1 takes polynomial time to solve the LP formula (Schrijver 1998). Step 3 takes O(m) time to round the edges of E S O L , and Step 4 takes O(m · kn log n)) to remove the redundant edges from E S O L , where O(k · n log n) is the time to run Suurballe and Tarjan’s algorithm to check the k-connectivity between s and t (Suurballe and Tarjan 1984). Therefore, the runtime of Algorithm 1 is polynomial in the worst case. For the approximation ratio of Algorithm 1, obviously E S O L contains only edges with xe ≥ 21 in the basic optimum solution χ , so we have

123

J Comb Optim



l(E S O L ) =



l(e) ≤

e∈E(G), xe ≥ 21

2xe · l(e) ≤ 2

e∈E(G), xe ≥ 12



xe · l(e).

(5)

e∈E(G)

 Then because e∈E(G) xe · l(e) is exactly the length of an optimum solution to LP (1), it is not larger than that of an optimum solution to kCSP:   xe · l(e) ≤ l(e), (6) e∈O P T

e∈E(G)

where O P T is an optimum solution to kCSP. Combining Inequality (5) and Inequality (6), we have l(E S O L ) ≤ 2 · l(O P T ). Similarly, we have w(E S O L ) ≤ 2 · w(O P T ) ≤ 2W . Therefore, the time complexity and approximation ratio of Algorithm 1 are as in the following theorem: Theorem 3 Algorithm 1 runs in polynomial time, and outputs a feasible solution to kCSP, with length and weight bounded by two times of that of an optimum solution to kCSP.

3 Proof of Lemma 2 Before the technique paragraphs, we would like first to give some definitions. Let χ be a basic optimum solution to LP (1), and G χ be the graph composed by the edges with xe > 0 in χ . We say e ∈ G χ is a full edge if and only if xe = 1. Let E f ull be the set of full edges of G χ . Let Er es = G χ \ E f ull be the set of edges with 0 < xe < 1 in the solution to LP (1) and Vr es be the set of the vertices of Er es . While no confusion arises, Er es also denotes the graph composed by the edges of Er es . The cases is similar for other edge sets such as E S O L . To prove Lemma 2, the key idea is first to show that each vertex in graph Er es is exactly incident with two edges of Er es (as Lemma 4). Based on this property, we then show that the edges with 1 > xe ≥ 21 , together with the edges with xe = 1, collectively k connect s and t. According to the schedule of the proof, we shall first focus on the properties for the edges in Er es only. In other words, we would like first to consider the following residual LP formula instead of LP (1). Compared to LP (1), the LP formula is against graph G but with the edges of xe = 0 or xe = 1 removed, and the constraints changed accordingly.  l(e)xe (7) min e∈Er es

subject to 

xe −

e∈δ + Er es (v)



∀e ∈ Er es :

xe −

e∈δ − Er es (v)

xe · w(e) ≤ W −

e∈Er es

123







1+

e∈δ + Z (v)

w(e)



 k for v = s 1= 0 for v ∈ Vr es \ {s, t}

(8)

e∈δ − Z (v)

(9)

e∈Z

0 ≤ xe ≤ 1.

(10)

J Comb Optim

Let χr es be χ except that the xe s of value 0 or 1 are removed. For example, χ = (x1 , x2 , x3 , x4 , x5 , x6 )T = (1, , 0, 13 , 23 , 1, 13 )T , then χr es = (x3 , x4 , x6 )T = ( 13 , 23 , 13 )T . Apparently, χr es is a basic solution to LP (7). Then we have the property of Er es as below: Lemma 4 Every vertex of Vr es is incident to exactly two edges in graph Er es . Proof Firstly, we shall show that every vertex v ∈ Vr es is incident to at least two edges in Er es . Suppose only one edge of Er es joins v (Note that v must be incident with at least Then on one hand, because 0 < xe < 1, we have 0 < one  edge of Er es to be in Vr es ). x = x < 1, i.e., e e e∈δ(v)∩Er es e∈Er es x e is not integral. On the other hand, following  / Er es is with the LP formula (1), e∈δ(v)∩G χ xe must be integral. Since every edge e ∈    xe = 1 or xe = 0, e∈δ(v)∩Er es xe = e∈δ(v)∩G χ xe − e∈δ(v)∩(G χ \Er es ) xe must be an integer. A contradiction. Secondly, we shall show that every vertex in Vr es is incident to at most two edges in Er es . Suppose there exists a vertex v0 ∈ Vr es with a degree of at least three, i.e. |δ − (v0 )| + |δ + (v0 )| ≥ 3. Then, on one hand, since every vertex of Vr es must be incident to at least 2 edges (as the first statement above), we have: ⎛ 1  − 1 |δ (v)| + |δ + (v)| ≥ ⎝ |Er es | = 2 2 v∈Vr es



v∈Vr es \{v0 }

2+



⎞ 3⎠ > |Vr es |.

v=v0

On the other hand, it remains to show |Vr es | ≥ |Er es | must hold, and obtain a contradiction. Since χr es is a basic optimum solution, according to the definition of a basic solution, at least |Er es | linear independent constraints of Inequality (8), (9) and (10) must be active at χr es , i.e., at least |Er es | linear independent constraints are satisfied at equality for χr es . Since all the edges in Er es are with 1 > xe > 0, there must be at least |Er es | active constraints within Inequality (2) and Inequality  linear independent xe · w(e) = W − e∈Z w(e) might hold (i.e., Inequality (3) might (3). Since e∈Er es

be active), at least |Er es | − 1 linear independent inequalities must be active within Inequality (2). However, Inequality (2) contains at most |Vr es | − 1 linear independent constraints. So |Vr es | − 1 ≥ |Er es | − 1, and hence |Vr es | ≥ |Er es | holds. This completes the proof.

Let Vr2es be the set of vertices with degree 2 or −2 in Er es , and Vr1es = Vr es \ Vr1es . Then following Lemma 4, the degree of v ∈ Vr1es is 0. That is, for each v ∈ Vr1es , Er es contains exactly an edge entering and an edge leaving v. Therefore, Er es is actually a set of paths between the vertices of Vr2es . Further, we have the following lemma: Lemma 5 The edges of Er es compose a set of paths Pr es between the vertices of Vr2es . For every v ∈ Vr2es , Pr es contains exactly two paths leaving v or entering v, and any two paths of Pr es share no common edges and no common vertices within Vr1es . Proof According to its definition, for every v ∈ Vr2es , Er es contains exactly two edges either entering or leaving v; while for v ∈ Vr1es , Er es contains exactly one edge entering v and one another edge leaving v. So following flow theory, for each v ∈ Vr2es , Er es

123

J Comb Optim

contains exactly two paths either entering or leaving v. In addition, Er es contains no cycles, since Er es is a subgraph of G χ which contains no cycles, because G χ is a minimum length fractional flow coming from s to t. Therefore, the edges of Er es compose exactly the paths of Pr es . It remains to show that the paths of Pr es are edge-disjoint. Since every v ∈ Vr1es is incident with two edges exactly, v can appear on only one path of Pr es . That is, any two distinct paths of Pr es share no common vertices of Vr1es . So the paths of Pr es are internal vertex-disjoint, and hence edge-disjoint. This completes the proof.

Now we can give the proof of the correctness of Lemma 2, i.e., to show that E S O L can k−connects s and t. Note that E S O L is exactly the set of edges with xe ≥ 21 in G χ . Suppose Lemma 2 is not true, then there must exist k − 1 edges, say e1 , . . . , ek−1 , which can separate s and t in E S O L . Then according to Lemma 6 as below, the flow between s and t wrt χ is at most of value k − 1. This contradicts with the fact that the flow (wrt χ ) is of value k, and completes the proof of Lemma 2. Lemma 6 Let χ be a basic optimum solution to LP (1), and e1 , . . . , ek−1 be k − 1 edges with 21 ≤ xei ≤ 1. Assume that e1 , . . . , ek−1 separate s and t in E S O L , then the flow wrt χ is at most of value k − 1. Proof Let G s ⊃ {s} be a component of E S O L \ {e1 , . . . , ek−1 }. Then {e1 , . . . , ek−1 } separate graph E S O L into G s and E S O L \ G S . W.l.o.g., assume e1 , . . . , eh are with 1 , p2 , . . . , p1 , p2 xe = 1, while eh+1 , . . . , ek−1 are with 21 ≤ xe < 1. Let ph+1 h+1 k−1 k−1 2 be the paths between vertices of Vr es in Er es . W.l.o.g., assume that e j ∈ p 1j for each j. Following Lemma 5, there exists exactly one another path in Er es , say p 2j , which leaves the same vertex as p 1j . Because the flow going through p 1j and p 2j is of value at most 1, the flow that contains the set of paths { pij |i ∈ {1, 2}, j ∈ {h + 1, . . . , k − 1}} is of value at most k − 1 − h. Besides, the flow going through {e1 , . . . , eh } is of value at most h. Therefore, the flow going through { pij |i ∈ {1, 2}, j ∈ {h + 1, . . . , k − 1}} and {e1 , . . . , eh } are at most of value k − 1. It remains to show that neither a full edge outside {e1 , . . . , eh } nor a path of Pr es outside { pij |i ∈ {1, 2}, j ∈ {h + 1, . . . , k}} leaves G s in graph G χ . Suppose otherwise, G s would be connected to a component of E S O L \ G s in E S O L \ {e1 , . . . , ek−1 }, as the two cases analyzed below. This contradicts with the assumption that edges of {e1 , . . . , ek−1 } separate G s and E S O L \ G s in E S O L . 1. Suppose there exists a full edge e ∈ / {e1 , . . . , eh } in G χ that leaves G s . Because / {e1 , . . . , ek−1 } e is a full edge, xe = 1 holds and hence e ∈ E S O L . Then, e ∈ connects G s and a component of E S O L \ G s , so {e1 , . . . , ek−1 } can not disconnect G s from all the other components. 2. Suppose there exists a path p ∈ Pr es \ { pij |i ∈ {1, 2}, j ∈ {h + 1, . . . , k}} that leaves G s at v. Following Lemma 5, there must be exactly one another path p  that leaves v in G χ . Then either flow p or p  is with value at least 21 . That is, either the edges of p or p  would belong to E S O L and connect G s with a component of E S O L \G s . So the removal of {e1 , . . . , ek−1 } can not disconnect G s and E S O L \G s in E S O L . This completes the proof.

123



J Comb Optim

Algorithm 2 An LP-rounding algorithm for the kCSP problem. Input: Er es with a new length b(e), a basic optimum solution χ to LP (1); Output: k disjoint st-paths. 1. E S O L ← E f ull ; /*E S O L is initially the set of edges with xe = 1 in G χ . */ 2. Divide Pr es into two path sets P1 , P2 , such that every two paths in the same path set Pi shares no common vertex of Vr1es ;   3. Select i, i ∈ {1, 2}, such that e∈E(Pi ) b(e) ≤ e∈E(P3−i ) b(e); 4. Return E S O L ← E(Pi ) ∪ E S O L .

4 An improved approximation algorithm for the kCSP problem Recall that in Sect. 2, Algorithm 1 adds every edge with xe ≥ 21 to the solution. However, not all the edges with xe ∈ [ 21 , 1] are good choices for constructing a solution to the kCSP problem. This section will give an improved rounding algorithm which uses a more sophisticated method to round edges, such that the algorithm is with a pseudo ratio (α, 2 − α). According to the definition of pseudo ratio in Sect. 1.2, the pseudo ratio (α, 2 − α) means that for any output solution of the algorithm, there always exists 0 ≤ α ≤ 2, such that the weight and length of the solution are bounded by α times and 2 − α times of that of an optimum solution, respectively. Assume that χ is a basic optimum solution to LP (1). The main idea of the improved algorithm is to select the edges with less length and weight, rather than to simply select the edges with 21 ≤ xe ≤ 1. To do this, the algorithm combines the length and weight as one new cost, and then selects a set of edges with the sum of new cost minimized, providing k connectivity between s and t. Let l(χ ) and w(χ ) be the length and weight of the basic optimum solution to LP (1). The new mixed length for edge l(e) w(e) e is b(e) = l(χ ) + w(χ ) . According to Lemma 5, the edges of Er es exactly compose a set of internal vertex disjoint paths Pr es = { pij |i ∈ {1, 2}, j ∈ {1, . . . , h}}, where p 1j and p 2j leaves a same i

vertex of Vr2es . Then the task is to choose h paths { p jj | j ∈ {1, . . . , h}} from Pr es to provide the k connectivity between s and t. According to Lemma 5, we could divide Pr es into two path sets P1 , P2 , such that every two paths in Pi share no common vertex (An easy division is to set P1 := { p 1j | j ∈ {1, . . . , h}}, P2 := Pr es \ P1 ). Then following the same line of the proof of Lemma 2, it can be shown that E f ull ∪ E(Pi ) provides k-connectivity between s and t, for either i = 1 or 2. Therefore, the main idea of our algorithm is to divide Pr es into two path sets P1 , P2 , and then select Pi  with smaller e∈E(Pi ) b(e) for i = 1, 2. Formally, the algorithm is as below: It remains to show the approximation ratio of the algorithm, which is stated as follows: Theorem 7 There exists a real number 0 ≤ α ≤ 2, such that the weight and length of E S O L are bounded by α and 2 − α times of that of the optimum solution of kCSP.   Proof According to Algorithm 2, e∈E(Pi ) b(e) ≤ e∈E(P3−i ) b(e) holds. Then since b(E S O L ) = b(E f ull ) + β · b(E(Pi )) + (1 − β) · b(E(Pi )) holds for any 0 ≤ β ≤ 1, we have

123

J Comb Optim

b(E S O L ) ≤ b(E f ull ) + β





b(e) + (1 − β)

e∈E(Pi )

b(e) ≤

e∈E(P3−i )



xe · b(e) ≤ 2.

e∈G χ

(11) Assume that the weight-sum of E S O L is α times of W , where α is a real number SOL ) and 0 ≤ α ≤ 2. Then b(E S O L ) = e∈E S O L b(e) = α + l(El(χ ) . From Inequality

SOL ) (11), α + l(El(χ ) ≤ 2 holds. Then, l(E S O L ) ≤ (2 − α) · l(χ ) ≤ (2 − α) · l(O P T ), where O P T is an optimum solution to kCSP. This completes the proof.



Note that (α, 2 − α) is only a pseudo ratio for Algorithm 2. That is, α can differ for different instances, and the actual ratio of Algorithm 2 should be still (2, 2), since α = 2 may hold for some instances while α = 0 may hold for some other instances. The later chapter will give an approximation with a better ratio via balancing the length and the weight of a solution.

5 An approximation with a single factor ratio O(ln n) This section will improve the approximation ratio of Theorem 7 to (1, ln n) by combining cycle cancellation and a novel auxiliary graph construction method when the lengths and weights of the edges are nonnegative integers. We shall first state the cycle cancellation method, then give the improved algorithm that is an enhancement to the cycle cancellation technology. 5.1 The cycle cancellation method Let E 1 and E 2 be two set of edges. Let E 1 ⊕ E 2 denote the edge set E 1 ∪ E 2 \ {e(u, v)|{e(u, v), e(v, u)} ⊆ E 1 ∪ E 2 }, i.e., the edge set E 1 ∪ E 2 with the pairs of parallel edges in opposite direction therein removed. Let P be a st-path. Then P = {e (v, u)|e(u, v) ∈ P}, i.e., P is the set of edges on path P with their direction reversed. Moreover, the weight of every edge of P is negatived and the length of every edge is set to 0, i.e., set w(e (v, u)) = −w(e(u, v)) and l(e (v, u)) = 0 for every edge e (u, v) ∈ P. Then we have the definition of residual graph as in the following:  = G r es (P1 , . . . , Pk ), with respect Definition 8 (Residual graph) A residual graph G to G and P1 , . . . , Pk ⊂ G, is graph G ∪ ( ∪ E(Pi )) \ ∪ E(Pi ), i.e., graph i=1, ..., k

i=1, ..., k

G except edges of P1 , . . . , Pk with their direction reversed, weight negatived, and length set to 0.1  is short for G  = G r es (P1 , . . . , Pk ). The cycle cancelWhile no confusion arises, G lation method is based on the following proposition. Proposition 9 Let P1 , . . . , Pk be k disjoint st-paths in G and O be an arbitrary cycle  Then {P1 , . . . , Pk } ⊕ O contains k disjoint st-paths in G. in residual graph G. 1 Note that G  may contain pairs of parallel edges in the same direction, which are probably with different

lengths and weights.

123

J Comb Optim

Proof Following the flow theory, we need only to show firstly that {P1 , . . . , Pk } ⊕ O contains an st-flow of value k, and secondly that the flow is a valid flow in G. Then since {P1 , . . . , Pk } ⊕ O is integral, it must contain k disjoint st-paths. For the first, because in {P1 , . . . , Pk } ⊕ O, s and t are respectively with degree k and −k, whilst every other vertex is with degree 0, {P1 , . . . , Pk } ⊕ O contains a flow of value k that goes from s to t. For the second, on one hand, every edge appears at most once in {P1 , . . . , Pk } ⊕ O (satisfying the capacity constraint), since {P1 , . . . , Pk } and O shares no common edges, and the paths of {P1 , . . . , Pk } are mutually edgedisjoint. On the other hand, {P1 , . . . , Pk } ⊕ O contains only edges of G, since every edge of {O1 , . . . , Oh } \ G has a parallel opposite counterpart in {P1 , . . . , Pk }. So

{P1 , . . . , Pk } ⊕ O contains a valid flow in G. These completes the proof. From the above proposition, the cycle cancellation method is the idea of iteratively improving the weight (or length) of the k disjoint paths using a negative weight (or  length) cycle in G. 5.2 The improved algorithm Let P1 , . . . , Pk be a solution resulted from Algorithm 2, violating the weight constraint. The key idea of the improved algorithm is generally a greedy approach, which  a “best” cycle O with negative weight, and then uses O to iteratively computes in G decrease the weight of P1 , . . . , Pk via cycle cancellation, until the weight of the k paths obeys the weight constraint. The key observation is as in the following: k Lemma 10 If i=1 w(Pi ) > W , then there always exists at least one cycle with  negative weight in G. Proof Let P1∗ , . . . , Pk∗ be an optimum solution to kCSP, and P1 , . . . , Pk be k disjoint st-paths. Because every vertex in graph {P1∗ , . . . , Pk∗ } ⊕ {P1 , . . . , Pk } is with degree 0, {P1∗ , . . . , Pk∗ } ⊕ {P1 , . . . , Pk } is exactly a set of edge-disjoint cycles, k k h say O1 , . . . , Oh . Note that i=1 w(Pi ) > W ≥ i=1 w(Pi∗ ), so i=1 w(Oi ) ≤ k W − i=1 w(Pi ) < 0 holds, and hence at least one cycle of {O1 , . . . , Oh } is with negative weight. This completes the proof.

Therefore, in detail, our algorithm is composed by a set of iterations. The ith iteration (i) (i) computes a “best” cycle Oi , and uses it to improve the k disjoint paths, P1 , . . . , Pk , (i) (i) towards an optimum solution (When i = 0, {P1 , . . . , Pk } is the output of Algoi ), ΔWi } rithm 2). A “best” cycle for the ith iteration is a cycle Oi with minimum max{w(O l(Oi ) k (i)  where ΔWi = W − j=1 w(P ). Then the formal layout of among all cycles in G, j the improved algorithm is as in Algorithm 3. The ratio Algorithm 3 is as stated below. It is proof is following a similar line of Guo et al. (2013). Theorem 11 Algorithm 3 outputs k disjoint st-paths, with total weight bounded by W and total length bounded by O(ln W ) · l(O P T ), where O P T is an optimum solution to the kCSP problem.

123

J Comb Optim

Algorithm 3 An improved algorithm for kCSP. Input: Graph G, specified vertices s and t, a length function l(e), a weight function w(e), and a weight bound W ∈ Z+ 0; Output: {P1 , . . . , Pk }, the set of edges that compose k disjoint st-paths. 1. Compute k disjoint st-paths P1 , . . . , Pk by Algorithm 2; (i) (i) 2. Set i ← 0 and {P1 , . . . , Pk } ← {P1 , . . . , Pk }; k (i) 3. While j=1 w(P j ) > W do (i)

(i)

 wrt to G and {P , . . . , P }; (a) Construct G 1 k   with minimum max{w(Oi ), ΔWi } , where ΔWi = W − k w(P (i) ); (b) Compute cycle Oi in G j=1 j l(Oi ) (c) If w(Oi ) ≥ 0, then return “infeasible”; /*The instance is infeasible.*/ else (i+1) (i+1) (i) (i) i. {P1 , . . . , Pk } ← {P1 , . . . , Pk } ⊕ Oi ; ii. i ← i + 1; (i)

(i)

4. Set {P1 , . . . , Pk } := {P1 , . . . , Pk }, terminate.

Proof We need only to consider the length of the k output paths. Since Algorithm 3 only outputs solutions with total weight bounded by W . Assume that Algorithm 3 runs in h iterations. We shall sum up the length increment in all h iterations, and show that the sum of the length is bounded. 1. Summing up the length increment of the first h − 1 iterations: Consider the jth iteration, 1 ≤ j ≤ h−1. Since the weight constraint remains violated, k w(O ) ( j) w(Pl ) > W , and w(O j ) > ΔW j . Then, since l(O jj) attains minimum we have l=1  and {P (1j) , . . . , P (k j) } ⊕ O P T compose exactly a set of cycles among all cycles in G  we have in G,

w(O j ) l(O j )

≤

k ( j) w(O P T )− l=1 w(Pl ) l(O P T )

l(O j ) ≤

≤

 j−1 ΔW0 − i=1 w(Oi ) . l(O P T )

That is,

w(O j ) · l(O P T ).  j−1 ΔW0 − i=1 w(Oi )

By summing up l(O j ) in the h − 1 iterations, we have: h−1  j=1

l(O j ) ≤ l(O P T ) ∗

h−1  j=1

w(O j ) .  j−1 ΔW0 − i=1 w(Oi )

Following the definition of Definite Integral, we have: h−1  j=1

w(O j ) ≤  j−1 ΔW0 − i=1 w(Oi )



h−1 ΔW0 − i=1 w(Oi ) ΔW0

1 d x. x

(12)

According to Algorithm 2, ΔW0 ≥ −W . Meanwhile, h−1 in the h − 1th iteration, the w(Oi ) ≤ −1. Hence, the total weight constraint is still violated, so ΔW0 − i=1 length increment in the first h − 1 iterations is bounded by:

123

J Comb Optim

Algorithm 4 Construction of auxiliary graph H .  wrt G and {P (i) , . . . , P (i) }, edge is with length l : e → Z+ and weight Input: Residual graph G 0 1 k w : e → Z, a weight constraint W ; Output: Auxiliary graph H . 1. For every vertex vl of V do Add to H vertices vl0 , . . . , vl2W ;

 2. For every edge e = v j , vl ∈ E do If w(e) ≥ 0 then     w(e) 2W −w(e) 2W Add to H the edges v 0j , vl , vl , each of which is with length l(e); , ..., vj Else     2W +w(e) −w(e) 0 Add to H the edges v 2W , vl , each of which is with length l(e). , ..., vj j , vl



h−1 ΔW0 − i=1 w(Oi )

ΔW0

1 dx ≤ x



−1

−W

1 d x = ln W. x

(13)

Therefore, the length increment of the first h − 1 iterations is not larger than l(O P T ) · ln W . 2. The length increment of the hth iteration: ΔWh h ), ΔWh } For the last iteration, max{w(O = l(O attains minimum among all cycles l(Oh ) h)  Then because {P (1j) , . . . , P (k j) } ⊕ O P T compose exactly a set of cycles in in G.  we have G,

ΔWh l(Oh )

≤

k ( j) w(O P T )− l=1 w(Pl ) l(O P T )

=

ΔWh l(O P T ) ,

and hence l(Oh ) ≤ l(O P T ).

So the total length increment is bounded by (1 + ln W ) · l(O P T ). According to Algorithm 2, the total length of its output is at most l(O P T ). Therefore, the total length of the output of Algorithm 3 is at most (2 + ln W ) · l(O P T ) = O(ln W ) · l(O P T ). This completes the proof.

Although the ratio is O(ln W ), we can improve the ratio to O(ln n) by employing the technique of developing a FPTAS in Garey and Johnson (1979). Moreover, the time complexity of Algorithm 3, as well as the runtime of the algorithm for computing O j in latter subsection, is pseudo polynomial. Similarly, the runtime of the algorithms can also be enhanced to polynomial. Since the technique is well-known and its application here is traditional, we would like to omit the details here. 5.3 Computation of cycle O j max{w(O ), ΔW }

j i This section will show how to compute a cycle O j with minimum for l(O j ) k (i) (i) (i)  wrt G and {P , . . . , P }. The key ΔWi = W − j=1 w(P j ) in residual graph G 1 k observation is that the hardness of computing O j comes from the bicriteria costs. So the key idea of is to construct an auxiliary graphs H , such that every negative weight  is corresponding to a path in H . Then by computing the paths in H , we can cycle in G  if there exists any. The full layout of the construction find negative weight cycles in G is as shown in Algorithm 4.

123

J Comb Optim

 is with nonnegative length, every edge in H is also Since every edge in graph G with nonnegative length according to Algorithm 4. Hence, it takes only polynomial time to compute a shortest path between any two vertices of H . So our algorithm roughly proceeds as below: 1. Compute the shortest paths P(vlj , v 0j ) from vlj to v 0j by Dijkstra’s algorithm, for all j ≤ n and 0 < l ≤ 2W in H , ; ΔWi } minimized; 2. Find a path P(v hj , vlj ), with max{l−h, h l l(P(v j , v j )

 that corresponds to P(v h , vl ), and select a cycle 3. Compute the set of cycles in G j j O j therein with

max{w(O j ), ΔWi } l(O j )

minimized.

The algorithm above needs to compute at most 2W · n shortest paths, each of which takes O(W · m + W · n log(W · n)) time to run Dijkstra’s algorithm (Korte and Vygen 2012). Other parts of the algorithm take trivial time compared to computing the shortest paths. Therefore, we have:  max{w(O j ), ΔWi } (i) Lemma 12 Let ΔWi = W − kj=1 w(P j ). A cycle O j , with minimum l(O j )  can be computed within runtime O(W 2 mn + W 2 n 2 log(nW )). in residual graph G, Now we would like to discuss why we develop the O(ln n)-approximation for kCSP. Note that there already exists an O(ln n)-approximation for the kBCP problem (Guo et al. 2013). Compared to kBCP, kCSP has a new difficulty: the exact value of l(O P T ) is unknown. Apparently, the difficulty can be overcome by doing an exhaustive search over all the possible values of l(O P T ). So a simple idea to obtain an O(ln n)−approximation is as below: 1. Set L := 1; 2. While true do Call the (1, ln n)-approximation of Guo et al. (2013) against the corresponding kBCP instance wrt the given weight constraint W and length constraint L; If the kBCP instance is infeasible then Set L := L + 1; Else return the first feasible solution, terminate. /*If L is too small, the corresponding kBCP instance would be infeasible. The first feasible solution is with minimum L. */ EndWhile It is easy to see the time complexity of the above algorithm is O(l(O P T ) · tk BC P ), where l(O P T ) is the length of an optimum solution to the kCSP problem and tk BC P is the runtime of the method for kBCP of Guo et al. (2013). A natural question is whether the time complexity of the above algorithm can be improved by applying binary search (or other search techniques) to find l(O P T ), the optimum value of L. Unfortunately, at least binary search cannot be simply applied here. Because the (1, ln n)-approximation of Guo et al. (2013) only computes approximated solutions, but exact optimum solutions are required for applying the binary search technique. Assuming that binary search iteratively divides the possible values of L into two divisions, we can not determine which division l(O P T ) is in, given the computed

123

J Comb Optim

approximated solutions. Therefore, compared to approximations via combining the method of Guo et al. (2013) and exhaustive search, our O(ln n)-approximation algorithm has a significantly improved runtime that is comparable to tk BC P .

6 Conclusion This paper investigated approximation algorithms for the k-disjoint constrained shortest paths (kCSP) problem. As the first contribution, this paper developed an improved approximation algorithm with bifactor ratio (2, 2) by rounding a basic optimum solution to the proposed LP relaxation of the kCSP problem. The algorithm was then improved by employing a more sophisticated round-up method, such that for any output solution there exists 0 ≤ α ≤ 2 that the weight and the length of the solution are bounded, respectively, by α and 2 − α times of that of a optimum solution. The ratio is further improved to (1, ln n) by novelly extending the technique of Guo et al. (2013). Acknowledgments This research was partially supported by Natural Science Foundation of China #61300025, Natural Science Foundation of Fujian Province #2012J05115, and Doctoral Funds of Ministry of Education of China for Young Scholars #20123514120013.

References Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice Hall, Englewood Cliffs Bhatia R, Kodialam M, Lakshman TV (2006) Finding disjoint paths with related path costs. J Comb Optim 12(1):83–96 Chao P, Hong S (2007) A new approximation algorithm for computing 2-restricted disjoint paths. IEICE Trans Inf Syst 90(2):465–472 Garey MR, Johnson DS (1979) Computers and intractability. Freeman, San Francisco Guo L, Shen H (2012) On the complexity of the edge-disjoint min-min problem in planar digraphs. Theor Comput Sci 432:58–63 Guo Longkun, Shen Hong (2013) On finding min-min disjoint paths. Algorithmica 66(3):641–653 Guo L, Hong S, Kewen L (2013) Improved approximation algorithms for computing k disjoint paths subject to two constraints. In: Du DZ, Zhang G (eds) COCOON. Springer, Heidelberg Korte B, Vygen J (2012) Combinatorial optimization, vol 21. Springer, Heidelberg Li CL, McCormick TS, Simich-Levi D (1989) The complexity of finding two disjoint paths with min-max objective function. Discrete Appl Math 26(1):105–115 Lorenz DH, Raz D (2001) A simple efficient approximation scheme for the restricted shortest path problem. Oper Res Lett 28(5):213–219 Misra S, Xue G, Yang D (2009) Polynomial time approximations for multi-path routing with bandwidth and delay constraints. In: IEEE INFOCOM 2009, p 558–566 Orda A, Sprintson A (2004) Efficient algorithms for computing disjoint QoS paths. In: IEEE INFOCOM, vol 1, p 727–738. Citeseer Schrijver A (1998) Theory of linear and integer programming. Wiley, New York Suurballe JW (1974) Disjoint paths in a network. Networks 4(2):125 Suurballe JW, Tarjan RE (1984) A quick method for finding shortest pairs of disjoint paths. Networks 14(2):325 Xu D, Chen Y, Xiong Y, Qiao C, He X (2006) On the complexity of and algorithms for finding the shortest path with a disjoint counterpart. IEEE/ACM Trans Netw 14(1):147–158 Xue G, Zhang W, Tang J, Thulasiraman K (2008) Polynomial time approximation algorithms for multiconstrained qos routing. IEEE/ACM Trans Netw 16(3):656–669

123