Let G = (V, E) be an undirected graph with a weight function and a cost function on edges. The constrained minimum spanning tree problem is to find a minimum cost spanning tree T in G such that the total weight in T is at most a given bound B. In this paper, we present two polynomial time approximation schemes (PTASs) for the constrained minimum spanning tree problem.

1. Introduction

Motivated by the applications of quality of service (QoS) routing and multicasting, several multiple criteria problems have been studied (see [1–6] and references therein). Marathe et al. [5] studied a class of bicriteria network design problems that are defined as follows. Given an undirected graph G = (V, E) and two independent minimization criteria with a bound on the first criterion, a generic bicriteria network design problem involves the minimization of the second criterion but satisfies the bound on the first criterion among all possible subgraphs from G [5]. They considered three different criteria that have total edge cost, diameter, and maximum degree of a graph. The total edge cost of a graph is the sum of the costs of all edges in the subgraph. The diameter of a graph is the maximum distance between any pair of nodes in the subgraph. The degree of a node is the number of nodes adjacent to this node, and the maximum degree of a graph is maximum over the degrees of all nodes in the subgraph. Let G = (V, E) be an undirected graph and a positive integer B. Two different nonnegative functions, weight and cost, associate on edges in E, respectively. The constrained minimum spanning tree (CMST) problem [7–10] is to find a minimum total cost spanning tree T in G such that the total weight in T is at most B. Aggarwal et al. [7] showed that the CMST problem is weakly NP-hard. Then Hong et al. [9] gave a pseudopolynomial time algorithm to solve the CMST problem. Moreover, some approximation algorithms have been proposed to solve the CMST problem [5, 8, 10].

Given two positive real numbers α and β, an (α, β)-approximation algorithm for the CMST problem is defined as a polynomial-time algorithm that produces a solution with the total weight at most α times the bound B and the total cost at most β times the total cost of optimal solution for the CMST problem. The approximation ratio is denoted by (α, β). An (α, β)-approximation algorithm for the CMST problem is called the polynomial time approximation scheme (PTAS) that produces a spanning tree with an approximation ratio of (1,1 + ε), for any constant ε > 0. For any constant ε > 0, Marathe et al. [5] gave a (1 + ε, 1 + 1/ε)-approximation algorithm for the CMST problem. Ravi and Goemans [10] presented a (2,1)-approximation algorithm to solve the CMST problem in O(|E | log ² | V | +|V | log ³ | V|) time and improved the ratio to (1 + ε, 1), where the time complexity is O(|V|^O(1/ε)(|E | log ² | V | +|V | log ³ | V|)) for any constant ε > 0. These algorithms are based on the Lagrangian relaxation. Hassin and Levin [8] employed Ravi and Goemans′ [10] algorithm with the matroid intersection strategy [11–13] to design a (1,1 + 5ε)-approximation algorithm in O((1/ε²) ^(1/ε) | V|³) time for the CMST problem. For other related bicriteria problems, Hassin [14] gave a fully polynomial time approximation scheme (FPTAS) for the restricted shortest path problem. The purpose of this problem is to find a minimum cost shortest path P from a source to a destination subject to the constraint that the total weight in P is at most B. Then, Lorenz and Raz [15] gave an improved FPTAS whose time complexity is O(|V| | E | loglog | V | +(|V| | E|)/ε) for the restricted shortest path problem. Further, Xue et al. [16] also designed an FPTAS with improved time complexity to O(|V| | E | logloglog | V | +(|V| | E|)/ϵ) for the restricted shortest path problem. If the graph is directed acyclic, and Ergun et al. [17] provided an improved FPTAS for the restricted shortest path problem with running time O((|V||E|)/ε). Chen and Xue [18, 19] used a similar method to design PTASs for the k-pair delay constrained minimum cost routing problem and the weight constrained Steiner tree problem in series-parallel graphs. These algorithms are based on the rounding and scaling strategy that is offered by Hassin [14]. In this paper, we present two polynomial time approximation schemes to find (1,1 + ε)-approximation ratio for the CMST problem. Applying the second PTAS to Hassin and Levin′s algorithm [8], the approximation ratio can be improved to (1,1 + 4ε) for the CMST problem.

The rest of this paper is organized as follows. In Section 2, we first describe a (1, (1 + ε) ²)-approximation algorithm for the CMST problem and then improve the approximation ratio to (1,1 + ε). Finally, we make a conclusion in Section 3.

2. PTASs for the Constrained Minimum Spanning Tree Problem

In this section, we first clarify a (1, (1 + ε) ²)-approximation algorithm for the CMST problem. Hassin and Levin [8] first used this algorithm to obtain a (1,2(1 + ε)) ratio for the CMST problem. Then they applied the Lagrangian relaxation and matroid intersection methods to improve the ratio to (1,1 + 5ε) in ) time. However, they did not describe the details of this algorithm. Then, we improve this approximation ratio into (1,1 + ε). Note that applying our algorithm, the approximation ratio of Hassin and Levin′s algorithm [8] can be improved to (1,1 + 4ε) ratio with the same time complexity. For convenience, we use C(H) (resp., W(H)) to denote the sum of the costs (resp., weights) of all edges in any subgraph H of G. Let T_OPT be the optimal solution of the CMST problem. For any constant ε > 0 and an integer B, Ravi and Goemans′ [10] algorithm, denoted by 𝒜_R(ε, B), produces a spanning tree T of the W(T) at most (1 + ε)B and of the C(T) at most C(T_OPT). Our algorithm first finds a cost of the lower bound, denoted by LB, and a cost of the upper bound, denoted by UB, for the CMST problem. Then, iteratively shrink this range between LB and UB until UB ≤ (1 + ε)LB. A trivial lower bound LB can be set to 1, and an upper bound UB can be set to |V | *C_max, in which C_max is the maximum edge cost in G. However, the range between the trivial lower bound and upper bound is too large (i.e., not polynomial in input size). We reduce the range by Lorenz and Raz′s method [15] such that UB ≤|V|* LB. First, let c₁, c₂, …, c_k be all the distinct costs of edges in G. G_j = (V, E_j) denotes the subgraph of G(V, E), where E_j is the set of edges with costs not greater than c_j. It is clear that G_k = G and G_j⊆G_j+1 for 1 ≤ j ≤ k − 1. For 1 ≤ j ≤ k, we can use Prim′s algorithm [20] to find a minimum weight spanning tree T_j in G_j. Let J be the smallest index j such that W(T_j) is no more than B. Then, finding the value c_J of a graph G can be done in O(|V|²log |V|) time by binary search and Prim′s algorithm [20]. Therefore, we have c_J ≤ C(T_OPT)≤|V | *c_J. Hence, we can let the initial UB be |V | *c_J and LB be c_J. If UB ≤ (1 + ε)LB, then C(T_J) ≤ UB ≤ (1 + ε)LB ≤ (1 + ε)C(T_OPT). Otherwise, we first swap the cost (resp., weight) to the weight (resp., cost) for each edge in G and find a value M between LB and UB. Then, apply algorithm 𝒜_R(ε, M) to find a spanning tree T in G. If the total weight of T is no more than B, let UB = (1 + ε)M; otherwise, let LB = M. Hence, the range between LB and UB is shrunk. Then, we repeatedly run the algorithm 𝒜_R(ε, M) until UB ≤ (1 + ε)LB. The next lemma shows that we can obtain either a lower bound M or an upper bound (1 + ε)M for the CMST problem after running 𝒜_R(ε, M).

Lemma 2.1. Given an instance of the CMST problem with a constant ε > 0 and an integer 𝒞, one swaps the cost (resp., weight) to the weight (resp., cost) for each edge and then applies algorithm 𝒜_R(ε, 𝒞) to find a spanning tree T. If W(T) ≤ B, then there is an upper bound (1 + ε)𝒞. Otherwise, one can obtain a lower bound 𝒞.

Proof. For convenience, we use T_𝒞 to denote the minimum weight spanning tree of G with total cost at most 𝒞. After running the algorithm 𝒜_R(ε, 𝒞), we have a spanning tree T with W(T) ≤ W(T_𝒞) and 𝒞(T)≤(1 + ε)𝒞 since the costs and weights of all edges are exchanged. Hence, if W(T) ≤ B, then 𝒞(T_OPT) ≤ 𝒞(T)≤(1 + ε)𝒞. Otherwise, W(T_𝒞) ≥ W(T) > B. Then we assume 𝒞(T_OPT) < C for contradiction. Hence, we have W(T_𝒞) ≤ W(T_OPT). However, W(T_OPT) ≤ B, and we have W(T_𝒞) ≤ B. Hence, 𝒞 must be less than or equal to C(T_OPT).

For clarification, we describe the (1, (1 + ε) ²)-approximation algorithm for the CMST problem as follows.

Algorithm PTAS-CMST Input: A graph G = (V, E) with a weight function and a cost function on edges, an integer bound B, and two real numbers ε > 0 and ρ > 0.

Output: A spanning tree T_APX of G subject to W(T_APX) ≤ B.

(1)
For each edge in E, swap cost to weight and weight to cost, respectively. end for
(2)
Let an initial upper bound UB = |V | *c_J and an initial lower bound LB = c_J.
(3)
If UB ≤ (1 + ε)LB, then let T_APX = T_J and return.

Else
(3.1)
Let L = LB and U = ⌈UB/(1 + ρ)⌉.
(3.2)
Repeat the following steps until the condition (1) U ≤ (1 + ε)L or (2) U ≤ L + 1 holds.
- (3.2.1)
  Let a middle value .
- (3.2.2)
  Use algorithm 𝒜_R(ρ, M) to find a spanning tree T.
- (3.2.3)
  /* if W(T) > B, then we have a lower bound M; else we have an upper bound (1 + ρ)M and C(T) is less than or equal to this upper bound. */

If W(T) ≤ B, then let U = M and T_APX = T; else let L = M.

The approximation ratio of Algorithm PTAS-CMST is shown in the next lemma.

Lemma 2.2. Algorithm PTAS-CMST returns a spanning tree T_APX with C(T_APX)≤(1 + ε)(1 + ρ)C(T_OPT).

Proof. Let the upper bound U_i, the middle value M_i, and the lower bound L_i be parameters at the beginning of the ith iteration of step (3.2) for Algorithm PTAS-CMST. Let T_i denote a spanning tree after running the i-th iteration of step (3.2.2). It is clear that L_i ≤ M_i ≤ U_i. Hence, U_i+1 ≤ U_i and L_i+1 ≥ L_i. Moreover, we have and U_i+1 = U_i when W(T_i) > B. Then, we also have and L_i+1 = L_i when W(T_i) ≤ B. Further, , or . Therefore, we have . Note that it successively narrows down the range between the lower bound L and the upper bound U after each iteration of step (3.2). After running the ith iteration of step (3.2.3), we obtain either a lower bound M_i or an upper bound (1 + ρ)M_i by Lemma 2.1. Let k be the number of iterations of step (3.2). After performing this algorithm, we have either U_k+1 ≤ (1 + ε)L_k+1 or U_k+1 ≤ L_k+1 + 1. For the former case, we have

()

For the latter case, we have

()

Let ρ be ε, and hence Algorithm PTAS-CMST achieves an approximation ratio of (1, (1 + ε) ²) for the CMST problem.

Therefore, we have the following theorem.

Theorem 2.3. The CMST problem admits a PTAS. For any constant ε > 0, a (1, (1 + ε) ²)-approximation algorithm for the CMST problem can be found in polynomial time.

Proof. By Lemma 2.2, Algorithm PTAS-CMST returns a (1, (1 + ε) ²)-approximation solution for the CMST problem. Next, we analyze the time complexity of Algorithm PTAS-CMST as follows. Let k be the number of iterations of step (3.2). We also let L₁ and U₁ be the initial lower bound and upper bound, respectively. Since , we have

()

Because (U_k/L_k)>(1 + ε) and U₁/L₁ ≤ (|V|/1 + ρ) + 1, we have k ≤ log _1/2log _{(|V|+1+ρ)/(1+ρ)}(1 + ε) + 1. Hence, k is O(loglog | V | − loglog(1 + ε)). Then, step (3.2.2) can be done in O(|V|^o(1/ρ)*(|E | log ² | V | +|V | log ³ | V|)) time by Ravi′s algorithm [10]. Hence, Algorithm PTAS-CMST is a polynomial time approximation scheme for the CMST problem.

Now, we improve the approximation ratio to (1,1 + ε) for the CMST problem. This algorithm is the modification of the one designed in [17] for the restricted shortest path problem.

Algorithm Modify-PTAS-CMST Input: A graph G = (V, E) with a weight function and a cost function on edges, an integer bound B, and two real numbers ε > 0 and 0 < γ < 1.

Output: A spanning tree T_APX of G subject to W(T_APX) ≤ B.

(1)
For each edge in E, swap cost to weight and weight to cost, respectively. end for
(2)
Let an initial upper bound UB = |V | *c_J and an initial lower bound LB = c_J.
(3)
IfUB ≤ (1 + ε)LB,then let T_APX = T_J and return.

Else
(3.1)
Let L = LB and U = UB.
(3.2)
Repeat the following steps until the condition (1) U ≤ (1 + ε)L or (2) U ≤ L + 1 holds.
- (3.2.1)
  Let a real number ρ = (U/L) ^γ − 1 and a middle value .
- (3.2.2)
  Use algorithm A_R(ρ, M) to find a spanning tree T.
- (3.2.3)
  /* if W(T) > B, then we have a lower bound M; else we have an upper bound (1 + ρ)M and C(T) is less than or equal to this upper bound. */

If W(T) ≤ B, then let U = (1 + ρ)M and T_APX = T; else let L = M.

The approximation ratio of Algorithm Modify-PTAS-CMST is shown in the next lemma.

Lemma 2.4. The spanning tree T_APX is a (1, 1 + ε)-approximation solution for the CMST problem.

Proof. Let the upper bound U_i, the middle value M_i, the lower bound L_i, and the real number ρ_i be parameters at the beginning of the ith iteration of step (3.2) for Algorithm Modify-PTAS-CMST. Let T_i denote a spanning tree after running the i-th iteration of step (3.2.2). If W(T_i) ≤ B, we have and L_i+1 = L_i. Otherwise, if W(T_i) > B, we have and U_i+1 = U_i. Hence, . Note that it successively narrows down the range between the lower bound L and the upper bound U after each iteration of step (3.2) since 0 < γ < 1. Let k be the number of iterations of step (3.2). After performing this algorithm, we have either U_k+1 ≤ (1 + ε)L_k+1 or U_k+1 ≤ L_k+1 + 1. For the former case, we have

()

For the latter case, we have

()

Therefore, we have the following theorem.

Theorem 2.5. The CMST problem admits a PTAS. For any constant ε > 0, a (1,1 + ε)-approximation algorithm for the CMST problem can be found in polynomial time.

Proof. Clearly, Algorithm Modify-PTAS-CMST returns a (1,1 + ε)-approximation solution for the CMST problem by Lemma 2.4. Next, we analyze the time complexity of Algorithm Modify-PTAS-CMST as follows. Let k be the number of iterations of step (3.2). We also let L₁ and U₁ be the initial lower bound and upper bound, respectively. Then, we have

()

since

Initially, U₁/L₁ = |V|. After running Algorithm Modify-PTAS-CMST, we have (U_k+1/L_k+1)≤(1 + ε). Step (3.2.2) can be done in O(|V|^o(1/ρ)*(|E | log ² | V | +|V | log ³ | V|)) time by Ravi′s algorithm [10]. Let I be the smallest index j such that , for 1 ≤ j ≤ k. For all 1 ≤ j ≤ I − 1, the time is . It is clear that (U_I/L_I) < 2^1/γ and (U_I−1/L_I−1) ≥ 2^1/γ. Hence, we have log _(γ+1)/2(1/(γ*log ₂ | V|)) + 1 ≥ I − 1 > log _(γ+1)/2(1/(γ*log ₂ | V|)) since . If I − 1 ≥ 1, the complexity is at most O(|V | (1 − log _((γ+1)/2)γ − log _{(γ + 1/2)}(log ₂ | V|))(|E | log ² | V | +|V | log ³ | V|)), for all 1 ≤ j ≤ I − 1. Then, for all I ≤ j ≤ k, the time complexity is . Since (U_k/L_k)>(1 + ε) with , we have k < log _(γ+1)/2(log (1 + ε)/log | V|) + 1. Moreover, (1/ρ_I) ≤ (1/(ρ_I+1)) ≤ ⋯≤(1/ρ_k). Hence we have the time complexity at most for all I ≤ j ≤ k. Because γ is a constant, the total time complexity is at most , where 1/ρ_k ≤ 1/((1 + ε) ^γ − 1), 0 < γ < 1.

Let ε = 1 and γ ≈ 1. Use Algorithm Modify-PTAS-CMST to find a feasible solution for the CMST problem with ratio (1,2). The total time complexity of this algorithm is at most . Then, we can apply Hassin and Levin′s [8] algorithm (i.e., the Lagrangian relaxation and matroid intersection), and the approximation ratio can be improved to (1,1 + 4ε) with the same time complexity of Hassin and Levin′s algorithm (i.e., O((1/ε²) ^(1/ε) | V|³)).

3. Conclusion

In this paper, we presented two polynomial time approximation schemes for the CMST problem. Using the second PTAS with the Lagrangian relaxation and matroid intersection, the approximation ratio of Hassin and Levin′s algorithm [8] can be improved to the ratio of (1,1 + 4ε). A open problem left in the paper could involve studying whether there exists a fully polynomial time approximation scheme for the CMST problem.

Acknowledgment

This work was supported in part by the National Science Council of the Republic of China under Contract NSC99-2221-E-133-003.

References

1 Chow C. H., On multicast path finding algorithms, 3, Proceedings of the 10th Annual Joint Conference of the IEEE and Communications Societies (IEEE INFOCOM ′91), 1991, Bal Harbour, Fla, USA, 1274–1283.
Google Scholar
2 Goel A., Ramakrishnan K. G., Kataria D., and Logothetis D., Efficient computation of delay-sensitive routes from one source to all destinations, 2, Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies, 2001, Anchorage, Alaska, USA, 854–858.
Google Scholar
3 Kadaba B. and Jaffe J., Routing to multiple destinations in computer networks, IEEE Transactions on Communications. (1983) 31, 343–351.
10.1109/TCOM.1983.1095818
Web of Science® Google Scholar
4 Kompella V. P., Pasquale J. C., and Polyzos G. C., Multicasting for multimedia applications, IEEE/ACM Transactions on Networking. (1993) 286–292.
10.1109/90.234851
Web of Science® Google Scholar
5 Marathe M. V., Ravi R., Sundaram R., Ravi S. S., Rosenkrantz D. J., and Hunt,H. B.III, Bicriteria network design problems, Journal of Algorithms. (1998) 28, no. 1, 142–171, 1627037, https://doi.org/10.1006/jagm.1998.0930, ZBL0906.68076.
10.1006/jagm.1998.0930
Web of Science® Google Scholar
6 Wang Z., On the complexity of quality of service routing, Information Processing Letters. (1999) 69, no. 3, 111–114, 1673584, https://doi.org/10.1016/S0020%2D0190(98)00206%2D3.
10.1016/S0020-0190(98)00206-3
Web of Science® Google Scholar
7 Aggarwal V., Aneja Y. P., and Nair K. P. K., Minimal spanning tree subject to a side constraint, Computers and Operations Research. (1982) 9, no. 4, 287–296.
10.1016/0305-0548(82)90026-0
Web of Science® Google Scholar
8 Hassin R. and Levin A., An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection, SIAM Journal on Computing. (2004) 33, no. 2, 261–268, https://doi.org/10.1137/S0097539703426775, 2048440, ZBL1112.90068.
10.1137/S0097539703426775
Web of Science® Google Scholar
9 Hong S.-P., Chung S.-J., and Park B. K., A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem, Operations Research Letters. (2004) 32, no. 3, 233–239, 2029380, https://doi.org/10.1016/j.orl.2003.06.003, ZBL1044.90061.
10.1016/j.orl.2003.06.003
CAS Web of Science® Google Scholar
10 Ravi R. and Goemans M., The constrained minimum spanning tree problem, 1097, Proceedings of the 5th Scandinavian Workshop on Algorithm Theory, 1996, 66–75, Lecture Notes in Computer Science.
Google Scholar
11 Chalasani P. and Motwani R., Approximating capacitated routing and delivery problems, SIAM Journal on Computing. (1999) 28, no. 6, 2133–2149, https://doi.org/10.1137/S0097539795295468, 1698938, ZBL0943.68076.
10.1137/S0097539795295468
Web of Science® Google Scholar
12 Cook W. J., Cunningham W. H., Pulleyblank W. R., and Schrijver A., Combinatorial optimization, 1998, John Wiley & Sons, New York, NY, USA, Wiley-Interscience Series in Discrete Mathematics and Optimization, A Wiley-Interscience Publication1490579.
Google Scholar
13 Lawler E. L., Combinatorial Optimization: Networks and Matroids, 1976, Holt, New York, NY, USA, 0439106.
Google Scholar
14 Hassin R., Approximation schemes for the restricted shortest path problem, Mathematics of Operations Research. (1992) 17, no. 1, 36–42, 1148776, https://doi.org/10.1287/moor.17.1.36, ZBL0763.90083.
10.1287/moor.17.1.36
Web of Science® Google Scholar
15 Lorenz D. H. and Raz D., A simple efficient approximation scheme for the restricted shortest path problem, Operations Research Letters. (2001) 28, no. 5, 213–219, 1845768, https://doi.org/10.1016/S0167%2D6377(01)00069%2D4, ZBL0992.90057.
10.1016/S0167-6377(01)00069-4
Web of Science® Google Scholar
16 Xue G., Zhang W., Tang J., and Thulasiraman K., Polynomial time approximation algorithms for multi-constrained QoS routing, IEEE/ACM Transactions on Networking. (2008) 16, 656–669.
10.1109/TNET.2007.900712
Web of Science® Google Scholar
17 Ergun F., Sinha R., and Zhang L., An improved FPTAS for restricted shortest path, Information Processing Letters. (2002) 83, no. 5, 287–291, 1910702, https://doi.org/10.1016/S0020%2D0190(02)00205%2D3, ZBL1051.68152.
10.1016/S0020-0190(02)00205-3
Web of Science® Google Scholar
18 Chen G. and Xue G., K-pair delay constrained minimum cost routing in undirected networks, Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ′01), 2001, Washington, DC, USA,, SIAM, 230–231, 1958413.
Google Scholar
19 Chen G. and Xue G., A PTAS for weight constrained Steiner trees in series-parallel graphs, Theoretical Computer Science. (2003) 304, no. 1–3, 237–247, 1992335, https://doi.org/10.1016/S0304%2D3975(03)00088%2D4, ZBL1044.68123.
10.1016/S0304-3975(03)00088-4
Web of Science® Google Scholar
20 Cormen T. H., Leiserson C. E., Rivest R. L., and Stein C., Introduction to Algorithms, 2001, 2nd edition, MIT Press, Cambridge, Mass, USA, 1848805.
CAS PubMed Google Scholar

Citing Literature

All articles

Polynomial Time Approximation Schemes for the Constrained Minimum Spanning Tree Problem

Abstract

1. Introduction

2. PTASs for the Constrained Minimum Spanning Tree Problem

3. Conclusion

Acknowledgment

References

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Polynomial Time Approximation Schemes for the Constrained Minimum Spanning Tree Problem

Abstract

1. Introduction

2. PTASs for the Constrained Minimum Spanning Tree Problem

3. Conclusion

Acknowledgment

References

Citing Literature

References

Related

Information