# The Capacity Expansion Path Problem in Networks

Authors: Jianping Li; Juanping Zhu
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

This paper considers the general capacity expansion path problem (GCEP) for the telecommunication operators. We investigate the polynomial equivalence between the GCEP problem and the constrained shortest path problem (CSP) and present a pseudopolynomial algorithm for the GCEP problem, no matter the graph is acyclic or not. Furthermore, we investigate two special versions of the GCEP problem. For the minimum number arc capacity expansion path problem (MN-CEP), we give a strongly polynomial algorithm based on the dynamic programming. For the minimum-cost capacity expansion shortest path problem (MCESP), we give a strongly polynomial algorithm by constructing a shortest paths network.


---

## Body

## 1. Introduction

Currently Chinese telecommunication operators are under the huge pressure of communication capacity and communication quality, followed by the rapidly increasing users. Shortest path problem plays an important role in the telecommunication networks. In this paper, we consider the network capacity expansion strategy for the telecommunication operators, called the general capacity expansion path problem (GCEP), given a weighted digraphD=(V,A;w,c,p) with n nodes, m arcs, and two fixed nodes s, t. For each arc e∈A, nonnegative w(e) is the weight, c(e) is the capacity, and nonnegative p(e) is the cost of expanding the capacity of the arc e by one unit. Given two positive W and d, find a path Ps,t from s to t to satisfy two constraints: (1) w(Ps,t)=∑e∈Ps,t‍w(e)≤W and (2) for some arc e∈A, if the capacity c(e)<d, we must expand the capacity of arc e to d. The objective is to minimize the total expansion cost ∑e∈Ps,t‍add(e)p(e) on the path Ps,t, where add(e)=d-c(e) if c(e)<d and add(e)=0 otherwise. In telecommunication network, W is the given maximum length of the path Ps,t, and d is the expected maximum number of the users. If the length of the path Ps,t exceeds W, the communication quality would drop quickly. If the capacity (or bandwidth) of the arc is not wide enough, the arc would be congested, and we have to expand this arc to the expected d.Krumke et al. [1] studied budget constrained network upgrading problems. The goal is how to find a minimum cost set of vertices to be upgraded so that the resulting network has a minimum spanning tree of weight no more than the budget. Their upgrading costs are on the vertices.Zhang et al. [2] studied the problem how to increase the capacities of the elements in an edge set E efficiently so that the capacity of a given family ℱ of subsets of E can be increased to the maximum extent, where the total cost for the increment of capacity is within a given budget bound D. Yang and Zhang [3] considered a class of bottleneck capacity expansion problems, which aimed to enhance bottleneck capacity to a certain level with minimum cost. There were two types of expanding models: arc expanding and node expanding. They emphasized the maximum capacity path problem. Our models are different from theirs. For example, when we consider the arc expansion cost of the path in the telecommunication network, on which each signal is sent from the source s via some transferring facility vi to the sink t, we must make sure that the transferring length does not exceed the length bound W.Different from our model and method, Seref et al. [4] studied an incremental optimization problem. They started from a feasible solution x0 and made an incremental change in x0 that would result in the greatest improvement in the objective function. For the incremental shortest path problem, they showed that the arc inclusion version is polynomially solvable whereas the arc exclusion version is NP-complete.In this paper, we present a proof of polynomial equivalence between the GCEP problem and the constrained shortest path problem (CSP), which leads to that the GCEP problem remainsNP-hard. We design a pseudopolynomial algorithm and a FPTAS to solve the GCEP problem. Then we study two special versions of the GCEP problem. For the first version, minimum number arc capacity expansion path problem (MNCEP), we present a strongly polynomial algorithm based on dynamic programming. For the second version, the minimum-cost capacity expansion shortest path problem (MCESP), we construct a shortest path network and present a strongly polynomial algorithm.


## 2. The Equivalence between the GCEP Problem and the CSP Problem

Motivated by the polynomial equivalence between the Hitchcock problem and the minimum-cost flow problem [5], we prove that the GCEP problem is polynomially equivalent to the constrained shortest path problem, which leads to Theorem 1. Hassin [6] studied the constrained (or restricted) shortest path problem (CSP) as follows. Let D=(V;A) be a weighted digraph with n nodes, m arcs, and two fixed nodes s, t. Each arc e∈A has a length c(e) and a transition time w(e). These numbers are assumed to be positive integers. For any path Ps,t from s to t in D, the length c(Ps,t) and transition time w(Ps,t) are defined as the sum of the lengths and transition times of all arcs on Ps,t, respectively. The CSP problem is to find the minimum length path Ps,t in D such that transition time w(Ps,t) along this path does not exceed a given bound W. For convenience, we denote a notation, by {D=(V,A;w,c;s,t);W}CSP, to represent an instance of the CSP problem. The CSP problem is a classical NP-hard problem [7]. To obtain Theorem 1, we use {D=(V,A;w,c,p;s,t);W;d}GCEP to represent an instance of the GCEP problem.Theorem 1.
The GCEP problem is polynomially equivalent to the CSP problem.Proof.
It is sufficient to prove that the GCEP problem can be transformed to the CSP problem in polynomial operations, and vice versa.
For any instanceℐ, say {D=(V,A;w,c,p;s,t);W;d}GCEP, of the GCEP problem, we construct an instance τ(ℐ) of the CSP problem: a digraph {D′=(V,A;w′,c′;s,t);W′}CSP consisting of the same structure as the digraph D with n nodes, m arcs, two fixed nodes s and t, and two positive d and W′(=W). For each arc e∈A, define two nonnegative w′(e)=w(e) and c′(e)=add(e)p(e), where add(e)=d-c(e) if c(e)<d and add(e)=0 otherwise. The objective is to find a path Ps,t from s to t in D′ such that ∑e∈Ps,t‍w′(e)≤W′ and the value of ∑e∈Ps,t‍c′(e) is minimized.
On the converse direction, for any instance𝒥, say {D′=(V,A;w′,c′;s,t);W′}CSP, of the CSP problem, we construct an instance α(𝒥) of the GCEP problem: a digraph D=(V,A;w,c,p;s,t;W,d)GCEP consisting of the same structure as the digraph D′ with n nodes, m arcs, a fixed positive integer d=2, and the bound W=W′. For each arc e∈A, define nonnegative w(e)=w′(e), c(e)=1, and p(e)=c′(e), which implies that add(e)=1 and add(e)p(e)=c′(e). The objective is to find a path Ps,t from s to t in D′ such that ∑e∈Ps,t‍w(e)≤W(=W′) and the value of ∑e∈Ps,t‍add(e)p(e)=∑e∈Ps,t‍c′(e) is minimized.
It is easy to prove the claim: there is an optimal solution to the instance𝒥 of the CSP problem with the optimal value k if and only if there is an optimal solution to the instance α(𝒥) of the GCEP problem with the optimal value k. Moreover, the transformation is executed in polynomial operations.Since the CSP problem isNP-hard, the proof of Theorem 1 implies that the GCEP problem is NP-hard, even if c(e)=1. And if p(e)=1, the GCEP problem is reduced to regular CSP problem.


## 3. A Pseudopolynomial Algorithm for the GCEP Problem

According to Theorem1, for any instance ℐ of the GCEP problem in the acyclic digraphs, by constructing an instance τ(ℐ) of the CSP problem and utilizing the FPTAS in [6, 8] for the CSP problem, we can get a FPTAS to solve the GCEP problem. Now for the GCEP problem, no matter acyclic digraphs or not, by applying the following dynamic programming method which is similar to the Bellman-Ford algorithm [9, 10], we give a pseudopolynomial algorithm. To describe our algorithm, for each node u∈V and two integers k≥0 and g≥0, define fk(u,g) to be the minimum length of an optimal path Ps,u from s to u with respect to the weight w, such that at most k arcs are traversed and the expansion cost along Ps,u is at most g. Set fk(u,g):=+∞ if no such path exists. For convenience, denote addcost(e)=add(e)p(e) as the expansion cost for each arc e∈A and W-path as the directed path if its weight is less than or equal to W. Set OPT to be the minimum capacity expansion cost of s-t  W-path.Algorithm 2 (EXACT(W)).
Comment. Return minimum capacity expansion path Ps,t from s to t with constraint w(Ps,t)≤W.
Begin
Step  1 (initialization). Set f0(s,g)=0 for each g≥0 and set f0(u,g)=+∞ if u≠s.
Step  2
Forg=1,2,…,OPT, do
Fork=1,2,…,n-1, do
For eachu∈V, do
f
k
(
u
,
g
)
=
min
{
f
k
-
1
(
u
,
g
), min{v∣(v,u)∈A,addcost(v,u)≤g}{fk-1(v,g-addcost(v,u))+w(v,u)}};
Iffn-1(t,g)≤W, output OPT=g and the path Ps,t, and exit.
End of Algorithm EXACT(W).Actually algorithm EXACT(W) is a dynamic programming algorithm, which generalizes the Bellman-Ford method [9, 10]. Note that OPT is not known but it satisfies OPT=min{g∣fn-1(t,g)≤W}. k is the maximum number of traversing arcs on the path from node s to u, and the algorithm enumerates each k(≤n-1) and each u∈V for fk(u,g). To get fn-1(t,g), the algorithm computes fk(u,g) first for g=1, k=1,…,n-1, and each u∈V, then for g=2,k=1,…,n-1, and each u∈V and so on, until the first value of g for which fn-1(t,g)≤W. According to the definition of fk(u,g), fk(t,g) is the minimum length of an optimal path Ps,t from s to t with respect to the weight w, such that at most k arcs are traversed and the expansion cost along Ps,t is at most g. fn-1(t,g)≤W indicates the length with respect to weight w on this optimal path Ps,t is less than and equal to W (optimal condition), and g≤OPT. Hence OPT is set to this value of g. So the complexity of algorithm EXACT(W) is 𝒪(OPT·mn2), and we obtain Theorem 3.Theorem 3.
For the GCEP problem, the algorithm EXACT(W) produces an optimal solution, and its time complexity is 𝒪(OPT·mn2).Moreover, the technique of rounding and scaling for acyclic digraphs in [8] is applied to our pseudopolynomial algorithm EXACT(W), and we can present an FPTAS in time 𝒪(n2m/ɛ) for the GCEP problem even in general digraphs, where ɛ>0. The construction of our FPTAS for general digraphs is similar to the one due to [8] for acyclic digraphs. The reader can find the algorithm in details from [8]; thus we omit it here.


## 4. Dynamic Programming Algorithm for the MNCEP Problem

In this section, we study the first special version of the GCEP problem, minimum number arc capacity expansion path problem (MNCEP), where for each arce∈A, p(e)=1, add(e)=1 if c(e)<d and add(e)=0 otherwise. Equivalently, the objective is to find a path Ps,t of D, on which the number of arcs to be expanded is minimized.Like the GCEP problem, no matter acyclic digraphs or not, by applying the method similar to Bellman-Ford algorithm [9, 10], we can design a strongly polynomial algorithm to solve the MNCEP problem. For each node u∈V, given two integers i≥0 and j≥0, define f(u,i,j) to be the minimum length of the path Ps,u from s to u with respect to the weight w, which traverses at most i arcs with exact j arcs to be expanded. Set f(u,i,j):=+∞ if no such path exists.Algorithm 4 (MNCEP).
Comment. Return the minimum number of arcs to be expanded on the path Ps,t from s to t with constraint w(Ps,t)≤W.
Begin
Step  1 (initialization). Set f(s,i,j)=0 and set f(u,i,j)=+∞ if u≠s.
Step  2
Fori=1,2,…,n-1, do
Forj=1,2,…,i, do
For each nodeu∈V, do f(u,i,j)=min{f(u,i-1,j),min{v∣(v,u)∈A,c(v,u)≥d}{f(v,i-1,j)+w(v,u)},min{v∣(v,u)∈A,c(v,u)<d}{d(v,i-1,j-1)+w(v,u)}}
Iff(t,i,j)≤W, then output OPT=j and the path Ps,t, and exit.
End of Algorithm MNCEP.The algorithm MNCEP is also based on dynamic programming. Different from algorithm EXACT(W), no unknown OPT appears in the algorithm. i is the maximum number of traversing arcs on the path from node s to u, and j is the exact number of arcs to be expanded on this path. So j≤i. The algorithm enumerates each i(≤n-1), each j≤i, and each u∈V till f(t,i,j)≤W. So the algorithm computes f(u,i,j) first for i=1, j=1,2,…,i, and each u∈V, then for i=2, j=1,2,…,i, and each u∈V, and so on, until the first value i≤n-1 for which f(t,i,j)≤W. Hence, output OPT=j. Thus, the algorithm runs in 𝒪(mn2) time. We obtain Theorem 5.Theorem 5.
For the MNCEP problem, the algorithm MNCEP produces an optimal solution, and its time complexity is𝒪(mn2).


## 5. Strongly Polynomial Algorithm for the MCESP Problem

The second special version of GCEP is the minimum-cost capacity expansion shortest path problem (MCESP). In MCESP problem, the boundW is set to be the shortest distance dist(s,t) from s to t in D, with respect to weight w. So the objective of MCESP problem is to find a shortest path Ps,t from s to t with respect to the weight w, such that the total expansion cost ∑e∈Ps,t‍add(e)p(e) on the path Ps,t is minimized, where add(e)=d-c(e) if c(e)<d and add(e)=0 otherwise. To solve this MCESP problem optimally, the shortest paths network plays an important role in the algorithm.Property 1 (see [11]).
Let the vector dist represent the shortest paths distances. Then a directed pathPs,v from the source node s to the node v is a shortest path if and only if dist(s,v)=dist(s,u)+w(u,v) for every arc (u,v)∈Ps,v.For convenience, setaddcost(e)=add(e)·c(e) as the capacity expansion cost for each arc e∈A.Algorithm 6 (MCESP).
Comment. Return the minimum-cost capacity expansion shortest path.
Begin
Step  1. Perform the breadth-first search in the digraph D, using the arcs to satisfy the equality dist(s,v)=dist(s,u)+w(u,v). Construct the shortest paths network D′=(V,A′;w,addcost) of D, where A′={(u,v)∈A∣dist(s,v)=dist(s,u)+w(u,v)}. The values of w and addcost in D′ remain the same as in D.
Step  2. Find the shortest path Ps,t from s to t in digraph D′, with respect to the arc capacity expansion cost addcost. Output OPT=addcost(Ps,t) and the path Ps,t.
End of Algorithm MCESP.Theorem 7.
The algorithm MCESP optimally solves the MCESP problem, and it runs in the time𝒪(n2).Proof.
Property1 implies the fact: if Ps,v is a shortest path from the source s to some node v, then dist(s,v)=dist(s,u)+w(u,v) for every arc (u,v)∈Ps,v. The converse is also true: if dist(s,v)=dist(s,u)+w(u,v) for every arc (u,v) in a directed path Ps,v from the source s to the node v, then Ps,v must be a shortest path. The algorithm MCESP searches all m arcs for dist(s,v)=dist(s,u)+w(u,v) in D. Hence, the new digraph D′ includes all minimum distance path from s to t in D, with respect to the weight w. The Step 2 of the algorithm selects the minimum cost capacity expansion path Ps,t in D′. Hence, the algorithm MCESP solves the MCESP problem optimally.
Step 1 of the algorithm needs𝒪(n2) steps to compute all d(s,v) by using Dijkstra algorithm for shortest paths. Step 2 needs 𝒪(m) steps to perform breadth-first search. Step 2 needs 𝒪(n2) steps as Step 1. Hence, the time complexity of the algorithm MCESP is 𝒪(n2).


## 6. Conclusion

In this paper, we focus on the general capacity expansion path problem for telecommunication operators, a new practical capacity expansion model. The polynomial equivalence between the GCEP problem and the CSP problem is proved. Then by utilizing dynamic programming technique and Bellman-Ford method [9, 10], we design a pseudopolynomial algorithm for the GCEP problem. We also present two special versions of the GCEP problem: the MNCEP problem and the MCESP problem. For the MNCEP problem, by using dynamic programming method and Bellman-Ford method, we design a strongly polynomial algorithm to solve it. For the MCESP problem, by constructing a shortest paths network, we design a strongly polynomial algorithm.For further work, we would investigate some other special versions of the GCEP problem and related algorithms, which exist in the current telecommunication networks.



---

*Source: 156901-2013-07-16.xml*