# Algorithms for the Shortest Path Improvement Problems under Unit Hamming Distance

Authors: Bingwu Zhang; Xiucui Guan; Chunyuan He; Shuguo Wang
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

In a shortest path improvement problem under unit Hamming distance (denoted by SPIUH), an edge weighted graph with a set of source-terminal pairs is given; we need to modify the lengths of edges by a minimum cost under unit Hamming distance such that the modified distances of the shortest paths are upper bounded by given values. The SPIUH problem on arborescent network is formulated as a 0-1 integer programming model. Some strongly polynomial time algorithms are designed for the problems on some special arborescent networks. Firstly, two greedy algorithms are proposed for problems on chain networks and special star-tree networks, respectively. Secondly, a strongly polynomial time algorithm is presented for the problem with a single source and constrained paths. Finally, a heuristic algorithm and its computational experiments are given for the SPIUH problem on general graphs.


---

## Body

## 1. Introduction

Due to theoretical and practical importance, the inverse shortest path problems and the shortest path improvement problems have been extensively studied in recent years. In such problems, an edge weighted graph with a set of source-terminal pairs is given; we need to modify the lengths of edges by a minimum cost under a given norm. In an inverse shortest path problem, the aim is to make a set of given paths become the shortest source-terminal paths, while in a shortest path improvement problem the aim is to make the modified distances of the shortest paths upper bounded by given values. Burton and Toint [1] solved the inverse shortest path problem under l2 norm by the nonlinear programming technique. Zhang et al. [2] proposed a column generation method for the inverse shortest path problem under l1 norm. Zhang and Lin [3] showed that the shortest path improvement problem under l1 norm is NP-complete and proposed polynomial time algorithms for the case of trees and the case of single source-terminal. Guan and Zhang [4, 5] studied network improvement problems for a tree-path system or a multicut by upgrading nodes in a directed tree. For detail of inverse optimization problems, the readers may refer to the survey paper by Heuberger [6].Since the inverse optimization problems under Hamming distance were first studied by He et al. [7], it has been investigated by many researchers (see, e.g., Zhang et al. [8–10], Duin and Volgenant [11], Guan and Zhang [12], Liu and Yao [13], and Jiang et al. [14]). Zhang et al. [8] showed that the shortest path improvement problem under Hamming distance (denoted by SPIH) is strongly NP-hard on general graphs and is still NP-hard even if the network is a chain network. So it is meaningful to design polynomial time algorithms for some special cases of the problems and to propose approximation and/or heuristic algorithms for the SPIH and the shortest path improvement problem under unit Hamming distance (denoted by SPIUH) on general graphs. That is the objective of this paper.LetG=(V,E) be a connected undirected network, where V is the vertex set, E={e1,e2,…,em} is the edge set. Let wi≥0 be the length of edge ei and li the lower bound on the modified length of ei, where i=1,2,…,m. Let {(sk,tk),k=1,2,…,r} be the set of source-terminal pairs of vertices. Denote by dw(u,v) the shortest distance connecting u to v under the length vector w. Let dk be the upper bound of the shortest distance connecting the source-terminal pair (sk,tk). The SPIUH problem is to find a new edge length vector w* satisfying l≤w*≤w such that the modified shortest distance dw*(sk,tk) is upper bounded by dk, and the total edge modification cost is minimized under unit Hamming distance, which can be formulated as a mathematical model shown below:
(1)min∑i=1m‍H(wi*,wi)s.t.dw*(sk,tk)≤dk,k=1,2,…,r,li≤wi*≤wi,i=1,2,…,m,
where the Hamming distance H(wi*,wi) is defined as
(2)H(wi*,wi)={1,ifwi*≠wi,0,ifwi*=wi.Zhang et al. show in [8] that SPIH problem can be transformed into a 0-1 knapsack problem in the special case when the given network is a chain network and r=1.Lemma 1 (see [8]).
The SPIH problem is NP-hard even if the network is a chain network.The shortest path improvement problems under Hamming distance have practical background. For example, a large earthquake happened in some towns. The relief supplies need to be quickly handed out to the people in the stricken area. However, many roads were badly damaged, and we have to repair the roads as soon as possible. Consider the networkG=(V,E) of towns, where v∈V denotes a town, e=(u,v)∈E denotes a road connecting u to v. Let wi and li be the travelling time through the road ei before/after ei is repaired. Note that some points of the road ei are damaged (rather than every point of the road being destroyed), so the repair time for the road ei may be a fixed amount ci instead of ci(wi-li). We need to transport the relief goods from some supplier town sk to some stricken town tk within the stipulated time. Our objective is to design a repair scheme satisfying the above transportation requirement such that the total repair time of repaired roads is minimized, which is just the shortest path improvement problem under Hamming distance.The rest of this paper is organized as follows. A 0-1 integer programming model of the SPIUH problem on arborescent networks is constructed in Section2. Some polynomial time algorithms are proposed for some special cases of the SPIUH problem on arborescent networks in Section 3. A heuristic algorithm and its computational experiment of the SPIUH problem on general graphs are given in Section 4. Conclusion and further research are given in Section 5.For convenience, we denote byPk a path from sk to tk and by w(Pk)=∑ei∈Pk‍wi the length of Pk under w. In Sections 2 and 3, we use the following useful notations. For the unique path Pk from sk to tk in G, if ei,ej∈Pk and ei appears before ej in the path Pk, then we denote it by ej<Pkei.


## 2. The SPIUH Problems on Arborescent Networks

In this section, we construct a 0-1 integer programming model for the SPIUH problem on arborescent networks (denoted by SPIUH-AN).The SPIUH-AN problem can be reformulated by the definition ofPk as follows:
(3)min∑i=1m‍H(wi*,wi)s.t.w*(Pk)≤dk,k=1,2,…,r,li≤wi*≤wi,i=1,2,…,m.We can check the feasibility of problem (3) based on the following lemma.Lemma 2.
Problem (3) is feasible if and only if l(Pk)≤dk for each k=1,2,…,r.Proof
Sufficiency. Suppose that l(Pk)≤dk for each k=1,2,…,r. Denote by Γ=⋃k=1rPk the union of given paths. Define a vector w-:E→Rm as follows:
(4)w-j={lj,ifej∈Γ,wj,otherwise.
It is easy to see that li≤w-i≤wi for each i=1,2,…,m. Furthermore, for each k=1,2,…,r, we have
(5)w-(Pk)=l(Pk)≤dk,
and thus w- is a feasible solution of problem (3).
Necessity. Suppose that w- is a feasible solution of problem (3). Note that Pk is the unique path from sk to tk and l≤w-; then we have
(6)l(Pk)≤w-(Pk)≤dk,k=1,2,…,r.Obviously, we have the following property on optimal solutions of (3).Lemma 3.
Ifw* is an optimal solution of problem (3), then w- defined below is also an optimal solution of problem (3):
(7)w-i={li,ifwi*≠wi,wi,ifwi*=wi.By Lemma3, the constraints w*(Pk)≤dk (k=1,2,…,r) in problem (3) are equivalent to
(8)∑ei∈Pk‍wi(1-H(wi*,wi))+∑ei∈Pk‍liH(wi*,wi)≤dk(k=1,2,…,r);
that is,
(9)∑ei∈Pk‍(wi-li)(1-H(wi*,wi))≤dk-∑ei∈Pk‍li=dk-l(Pk)(k=1,2,…,r).For each edgeei, if we define a 0-1 variable xi as follows:
(10)xi={1,ifthelengthofedgeeiisnotreduced,0,ifthelengthofedgeeiisreduced,
and let wi0=wi-li, dk0=dk-l(Pk), then problem (3) is equivalent to solving the problem below:
(11)min∑i=1m‍(1-xi)s.t.∑ei∈Pk‍wi0xi≤dk0,k=1,2,…,r,xi=0,1,i=1,2,…,m.As a conclusion, we have the following theorem.Theorem 4.
The SPIUH-AN problem is equivalent to solving the 0-1 integer programming problem (11). An optimal solution w* of the SPIUH-AN problem can be given by (12), and the optimal objective value is ∑i=1m(1-xi*), where x* is an optimal solution of problem (11):
(12)wi*={li,ifxi*=0,wi,ifxi*=1.


## 3. Some Special Cases of the SPIUH-AN Problem

In this section, we consider some special cases of SPIUH problem on arborescent networks. In Section3.1, we design greedy algorithms for the SPIUH problems on chain networks and special star-tree networks. In Section 3.2, we present a strongly polynomial time algorithm for the SPIUH problem with a single source and a special constraint on paths.


### 3.1. The SPIUH Problem on Special Star-Tree Networks

In this subsection, we first study the SPIUH problem on a chain network, whereG is a chain network and (s1,t1) is the only source-terminal pair. We design a greedy algorithm for the SPIUH problem on a chain network. The main idea is to reduce the length of the edge with the current largest value wi0 to li in each iteration.Algorithm 5 (a greedy algorithm).
Consider the following.Input: A chain G with a source-terminal pair (s1,t1), two edge length vectors l,w and a value d1.Step  1: If l(E)>d1, then output that the instance is infeasible, stop.Step  2: Let w0=w-l. Rearrange the values of w0 in a non-increasing order, that is, wj10≥wj20≥⋯≥wjm0.Step  3: Let p=0, and W=w(P1).Step  4: While W>d1 do
Putp=p+1, and W=W-wjp0.Step  5: Output an optimal solution w* defined below:
(13)wjq*={ljq,if1≤q≤p,wjq,otherwise.
It is easy to see that the main computation is to sort the values ofw0, and hence the time complexity of Algorithm 5 is O(mlogm).Next, we consider the SPIUH problem on a special star-tree networkG, where any two source-terminal paths of G have no common edges. Such a problem is denoted by SPIUH-ST. See Figure 1 for example; there are three source-terminal paths (s1,t1), (s2,t2), and (s3,t3).Figure 1
An example of a star tree for the SPIUH-ST problem.Obviously, the set of source-terminal paths is the union of edge-disjoint chains in the SPIUH-ST problem. Now we extend the greedy algorithm for SPIUH problem on a chain network to the SPIUH-ST problem.Algorithm 6.
Consider the following.Input: A star-tree network G with a set {(sk,tk)∣k=1,2,…,r} of source-terminal pairs, two edge length vectors l,w and a set {dk∣k=1,2,…,r} of values.Step  1: Let w0=w-l and S=∅. Rearrange the values of w0 in a non-increasing order, that is, wj10≥wj20≥⋯≥wjm0.Step  2: For k=1 to r do
Ifl(Pk)>dk, then output that the instance is infeasible, stop.Else run Steps 3, 4, 5 in Algorithm5 to solve the problem on the chain network Pk. Denote the optimal solution on Pk by {w-i∣ei∈Pk}, and let S=S∪{ei∣ei∈Pk,w-i=li,andwi0≠0}.Step  3: Output the optimal solution w* and the optimal objective value |S| of the SPIUH-ST problem, where
(14)wi*={li,ifei∈S,wi,otherwise.Now we analyze the time complexity of Algorithm 6. Sorting the values of w0 in Step 1 can be done in O(mlogm) operations. In Step 2, there are r iterations and there are O(|Pk|) operations in each iteration. Let D=max1≤k≤r|Pk|. Then Algorithm 6 can be done in
(15)O(mlogm+rD)=O(mlogm+rm)=O(m(r+logm))
operations. We sum up the above results in the following theorem.Theorem 7.
The shortest path improvement problems on star-tree networks under unit Hamming distance can be solved by Algorithm6 in O(m(r+logm)) time, where r is the number of source-terminal pairs.Remark 8.
There is a special case of the SPIUH-ST problem in whichG is a star-tree network with a central vertex sc such that there are no common edges on the paths from sc to all leaves of the tree, and the central vertex sc is the common source of all the source-terminal pairs; that is, sk=sc for each k=1,2,…,r. Hence, we only need to call Algorithm 5 in r times to solve the problem, and its time complexity is also O(m(r+logm)).


### 3.2. The SPIUH Problem with a Single Source and Constrained Paths

In this subsection, we consider the SPIUH problem with a single source and a special constraint on paths, wheresk=s for each k=1,2,…,r, and the path Pk satisfies the following constraint:
(16)ifei<Pkeqand|Qi|<|Qq|,thenwehavewi0≤wq0,
where Qi={tk∣ei∈Pk,k=1,2,…,r} is the set of terminals tk of path Pk which passes through ei. We call such a network an arborescent network with a single source and a special constraint on paths, which is denoted by SSCP. Such a problem is denoted by SPIUH-SSCP. The SPIUH problem with a single source and without the constraint condition (16) is denoted by SPIUH-SS.For example, given is a networkG=(V,E) in Figure 2, where V={s,v1,v2,t1,t2,t3}, E={ei∣i=1,2,…,5}, and ci=1 for each i=1,2,…,5. If w=(2,3,2,1,2), l=(0,0,0,0,0), and d=(3,3,3) (see Figure 2(a)), then it is an instance of SPIUH-SSCP problem. However, if w=(1,1,3,3,3), l=(0,0,0,0,0), and d=(3,3,3) (see Figure 2(b)), then we have e3<P1e1 and |Q3|=1<|Q1|=3, but w10=1<w30=3. Hence it is an instance of SPIUH-SS problem, but not an instance of SPIUH-SSCP problem. Next we give a polynomial time algorithm to solve the SPIUH-SSCP problem.Examples of arborescent networks with a single source.
(a)
(b)Algorithm 9.
Consider the following.Input: An arborescent network G with a single source s and constrained paths Pk from s to tk  (k=1,2,…,r), two edge length vectors l,w and a set {dk∣k=1,2,…,r} of values.Step1: Let w0=w-l and S=∅.Step2: For k=1 to r do
Ifl(Pk)>dk, then output that the instance is infeasible, stop.Else letdk=dk-w0(Pk∩S) and let wi′=li if ei∈Pk∩S and wi′=wi if ei∈Pk∖S. Call Algorithm 5 to solve the problem on the chain network Pk with respect to the length vector w′ and dk. In Step 2 of Algorithm 5, we let w0=w′-l, then for all ei∈Pk, rearrange the values wi0=wi′-li in a non-increasing order, and if there are two values are equal (let's say wp0 and wq0), and ep appears before eq in the direct path Pk from s to tk, then wp0 will always appear before wq0 in the non-increasing order. (This sorting method is called stable sorting method).
Denote byw- the optimal solution to the problem on Pk. Put S=S∪{ej∣ej∈Pk,w-j=lj,andwi′≠lj}.Step3: Output the optimal solution w* and optimal objective value |S| of the SPIUH-SSCP problem, where
(17)wj*={lj,ifej∈S,wj,otherwise.Lemma 10.
If the SPIUH-SSCP problem is feasible, then there is an optimal solutionα=(α1,α2,…,αm) of the SPIUH-SSCP problem satisfying the following.(1)
If there exists pathPk, ei∈Pk and eq∈Pk, such that ei<Pkeq, 0<wi0≤wq0, and αi=li, then we have αq=lq.(2)
If there exists pathPk, ei∈Pk, and eq∈Pk such that eq<Pkei, 0<wi0<wq0, and αi=li, then we have αq=lq.Proof.
Supposeβ=(β1,β2,…,βm) is an optimal solution of the SPIUH-SSCP problem. By Lemma 3, γ=(γ1,γ2,…,γm) defined below is also an optimal solution of the SPIUH-SSCP problem:
(18)γj={lj,ifβj≠wj,wj,ifβj=wj.(1)
If there exists a pathPk, ei∈Pk and eq∈Pk, such that ei<Pkeq, 0<wi0≤wq0, γi=li, and γq=wq, because |Qq|≥|Qi| and reducing the weight of eq first is better, or at least not worse, than reducing that of ei, then we can get that α is also an optimal solution of the SPIUH-SSCP problem, where
(19)αj={wi,ifj=i,lq,ifj=q,γj,otherwise.(2)
If there exists a pathPk, ei∈Pk and eq∈Pk, such that eq<Pkei, 0<wi0<wq0, γi=li, and γq=wq, because by (16) we know that |Qi|=|Qq| and reducing the weight of eq first is better, or at least not worse, than reducing that of ei, then we can get that α is also an optimal solution of the SPIUH-SSCP problem, where
(20)αj={wi,ifj=i,lq,ifj=q,γj,otherwise.Thus repeating the above operations, we can get an optimal solution α of the SPIUH-SSCP problem that satisfies the property in Lemma 10.Theorem 11.
If the SPIUH-SSCP problem is feasible, then Algorithm9 outputs an optimal solution w* of the SPIUH-SSCP problem in O(m(r+logm)) time.Proof.
If the SPIUH-SSCP problem is feasible, then it is not difficult to show that the solutionw* obtained by Algorithm 6 is a feasible solution of the SPIUH-SSCP problem.
Next we show thatw* obtained by Algorithm 9 satisfies properties (1) and (2) in Lemma 10. Note that we run Step 2 of Algorithm 5 for the path Pk by using stable sorting method in the kth iteration of for-loop in Algorithm 9 for any 0≤k≤r. When ei is added to S in the kth iteration of for-loop in Algorithm 9, we consider the following two cases.
(1) If there is aneq satisfying ei<Pkeq and 0<wi0≤wq0, then by the greedy property of Algorithm 9 (i.e., if ei<Pkeq and 0<wi0≤wq0, then eq is added to S before ei is added to S), we have eq∈S. Hence, for any wi*=li (i.e., ei∈S), if ei<Pkeq, 0<wi0≤wq0, then we have wq*=lq (i.e., eq∈S).
(2) If there is aneq∈Pk such that eq<Pkei, 0<wi0<wq0, then by the greedy property of Algorithm 9 (i.e., if eq<Pkei, 0<wi0<wq0, then eq is added to S before ei is added to S), we have eq∈S. Hence, we have wq*=lq.
Hence,w* obtained by Algorithm 9 is a feasible solution of the SPIUH-SSCP problem that satisfies properties (1) and (2) in Lemma 10.
Suppose thatα is the optimal solution of the SPIUH-SSCP problem which satisfies the property (1) and (2) in Lemma 10. Now we show that for each eq∈E, if wq0>0 and wq*=lq, then αq=lq. Suppose wq*=lq (i.e., eq∈S); we consider the following three cases.
Case  1. If there exist a path Pk and an edge ei∈Pk such that ei<Pkeq, 0<wi0≤wq0, and αi=li, then because the optimal solution α of the SPIUH-SSCP problem satisfies property (1) in Lemma 10, we can get that αq=lq.
Case  2. If there exist a path Pk and an edge ei∈Pk such that eq<Pkei, 0<wi0<wq0, and αi=li, then because the optimal solution α of the SPIUH-SSCP problem satisfies property (2) in Lemma 10, we can get that αq=lq.
Case  3. If for each Pk and for each ei∈Pk such that (1) ei<Pkeq, 0<wi0≤wq0 or (2) eq<Pkei, 0<wi0<wq0, we have αi=wi. Note that wq*=lq (i.e., eq∈S); suppose eq is added to S in the kth iteration of for-loop in Algorithm 9; let Ω={ei∣ei∈Pk,0<wq0<wi0}∪{ei∣ei∈Pk, eq<Pkei,0<wq0=wi0}, Θ=Pk∖Ω={eq}∪Γ, where Γ={ei∣eq<Pkei,0≤wi0<wq0}∪{ei∣ei<Pkeq,0≤wi0≤wq0}; then ∑ei∈Ωli+∑ei∈Θwi>dk (otherwise, eq∉S). Note that we have the assumption that αi=wi for each ei∈Γ, if αq=wq; then
(21)α(Pk)=∑ei∈Ω‍αi+∑ei∈Θ‍αi=∑ei∈Ω‍αi+αq+∑ei∈Γ‍αi=∑ei∈Ω‍αi+wq+∑ei∈Γ‍wi≥∑ei∈Ω‍li+∑ei∈Θ‍wi>dk.
This contradicts that α is an optimal solution of the SPIUH-SSCP problem, so αq=lq.
Hence, for eacheq∈E, if wq0>0 and wq*=lq, then αq=lq. That is, the objective value of w* is not greater than the objective value of α. Note that α is an optimal solution of the SPIUH-SSCP problem, so w* is an optimal solution of the SPIUH-SSCP problem.The time complexity analysis is similar to that of Theorem7.Example 12.
As shown in Figure2(a), let w=(2,3,2,1,2), l=(0,0,0,0,0), and d=(3,3,3). The optimal solution of the SPIUH-SSCP problem generated by Algorithm 9 is w*=(0,0,2,1,2), and the optimal objective value is 2.Remark 13.
Note that Algorithm9 cannot always obtain an optimal solution of the SPIUH-SS problem. For example, as shown in Figure 2(b), let w=(1,1,3,3,3), l=(0,0,0,0,0), and d=(3,3,3). In this case, it is an instance of SPIUH-SS problem, but not an instance of SPIUH-SSCP problem. The solution generated by Algorithm 9 is w*=(1,1,0,0,0), whose objective value is 3. But the optimal solution is α=(0,0,3,3,3), and the optimal objective value is 2.So it is meaningful to design efficient algorithms for the SPIUH-SS problem. We guess that the SPIUH-SS problem has strongly polynomial time algorithms.


## 3.1. The SPIUH Problem on Special Star-Tree Networks

In this subsection, we first study the SPIUH problem on a chain network, whereG is a chain network and (s1,t1) is the only source-terminal pair. We design a greedy algorithm for the SPIUH problem on a chain network. The main idea is to reduce the length of the edge with the current largest value wi0 to li in each iteration.Algorithm 5 (a greedy algorithm).
Consider the following.Input: A chain G with a source-terminal pair (s1,t1), two edge length vectors l,w and a value d1.Step  1: If l(E)>d1, then output that the instance is infeasible, stop.Step  2: Let w0=w-l. Rearrange the values of w0 in a non-increasing order, that is, wj10≥wj20≥⋯≥wjm0.Step  3: Let p=0, and W=w(P1).Step  4: While W>d1 do
Putp=p+1, and W=W-wjp0.Step  5: Output an optimal solution w* defined below:
(13)wjq*={ljq,if1≤q≤p,wjq,otherwise.
It is easy to see that the main computation is to sort the values ofw0, and hence the time complexity of Algorithm 5 is O(mlogm).Next, we consider the SPIUH problem on a special star-tree networkG, where any two source-terminal paths of G have no common edges. Such a problem is denoted by SPIUH-ST. See Figure 1 for example; there are three source-terminal paths (s1,t1), (s2,t2), and (s3,t3).Figure 1
An example of a star tree for the SPIUH-ST problem.Obviously, the set of source-terminal paths is the union of edge-disjoint chains in the SPIUH-ST problem. Now we extend the greedy algorithm for SPIUH problem on a chain network to the SPIUH-ST problem.Algorithm 6.
Consider the following.Input: A star-tree network G with a set {(sk,tk)∣k=1,2,…,r} of source-terminal pairs, two edge length vectors l,w and a set {dk∣k=1,2,…,r} of values.Step  1: Let w0=w-l and S=∅. Rearrange the values of w0 in a non-increasing order, that is, wj10≥wj20≥⋯≥wjm0.Step  2: For k=1 to r do
Ifl(Pk)>dk, then output that the instance is infeasible, stop.Else run Steps 3, 4, 5 in Algorithm5 to solve the problem on the chain network Pk. Denote the optimal solution on Pk by {w-i∣ei∈Pk}, and let S=S∪{ei∣ei∈Pk,w-i=li,andwi0≠0}.Step  3: Output the optimal solution w* and the optimal objective value |S| of the SPIUH-ST problem, where
(14)wi*={li,ifei∈S,wi,otherwise.Now we analyze the time complexity of Algorithm 6. Sorting the values of w0 in Step 1 can be done in O(mlogm) operations. In Step 2, there are r iterations and there are O(|Pk|) operations in each iteration. Let D=max1≤k≤r|Pk|. Then Algorithm 6 can be done in
(15)O(mlogm+rD)=O(mlogm+rm)=O(m(r+logm))
operations. We sum up the above results in the following theorem.Theorem 7.
The shortest path improvement problems on star-tree networks under unit Hamming distance can be solved by Algorithm6 in O(m(r+logm)) time, where r is the number of source-terminal pairs.Remark 8.
There is a special case of the SPIUH-ST problem in whichG is a star-tree network with a central vertex sc such that there are no common edges on the paths from sc to all leaves of the tree, and the central vertex sc is the common source of all the source-terminal pairs; that is, sk=sc for each k=1,2,…,r. Hence, we only need to call Algorithm 5 in r times to solve the problem, and its time complexity is also O(m(r+logm)).


## 3.2. The SPIUH Problem with a Single Source and Constrained Paths

In this subsection, we consider the SPIUH problem with a single source and a special constraint on paths, wheresk=s for each k=1,2,…,r, and the path Pk satisfies the following constraint:
(16)ifei<Pkeqand|Qi|<|Qq|,thenwehavewi0≤wq0,
where Qi={tk∣ei∈Pk,k=1,2,…,r} is the set of terminals tk of path Pk which passes through ei. We call such a network an arborescent network with a single source and a special constraint on paths, which is denoted by SSCP. Such a problem is denoted by SPIUH-SSCP. The SPIUH problem with a single source and without the constraint condition (16) is denoted by SPIUH-SS.For example, given is a networkG=(V,E) in Figure 2, where V={s,v1,v2,t1,t2,t3}, E={ei∣i=1,2,…,5}, and ci=1 for each i=1,2,…,5. If w=(2,3,2,1,2), l=(0,0,0,0,0), and d=(3,3,3) (see Figure 2(a)), then it is an instance of SPIUH-SSCP problem. However, if w=(1,1,3,3,3), l=(0,0,0,0,0), and d=(3,3,3) (see Figure 2(b)), then we have e3<P1e1 and |Q3|=1<|Q1|=3, but w10=1<w30=3. Hence it is an instance of SPIUH-SS problem, but not an instance of SPIUH-SSCP problem. Next we give a polynomial time algorithm to solve the SPIUH-SSCP problem.Examples of arborescent networks with a single source.
(a)
(b)Algorithm 9.
Consider the following.Input: An arborescent network G with a single source s and constrained paths Pk from s to tk  (k=1,2,…,r), two edge length vectors l,w and a set {dk∣k=1,2,…,r} of values.Step1: Let w0=w-l and S=∅.Step2: For k=1 to r do
Ifl(Pk)>dk, then output that the instance is infeasible, stop.Else letdk=dk-w0(Pk∩S) and let wi′=li if ei∈Pk∩S and wi′=wi if ei∈Pk∖S. Call Algorithm 5 to solve the problem on the chain network Pk with respect to the length vector w′ and dk. In Step 2 of Algorithm 5, we let w0=w′-l, then for all ei∈Pk, rearrange the values wi0=wi′-li in a non-increasing order, and if there are two values are equal (let's say wp0 and wq0), and ep appears before eq in the direct path Pk from s to tk, then wp0 will always appear before wq0 in the non-increasing order. (This sorting method is called stable sorting method).
Denote byw- the optimal solution to the problem on Pk. Put S=S∪{ej∣ej∈Pk,w-j=lj,andwi′≠lj}.Step3: Output the optimal solution w* and optimal objective value |S| of the SPIUH-SSCP problem, where
(17)wj*={lj,ifej∈S,wj,otherwise.Lemma 10.
If the SPIUH-SSCP problem is feasible, then there is an optimal solutionα=(α1,α2,…,αm) of the SPIUH-SSCP problem satisfying the following.(1)
If there exists pathPk, ei∈Pk and eq∈Pk, such that ei<Pkeq, 0<wi0≤wq0, and αi=li, then we have αq=lq.(2)
If there exists pathPk, ei∈Pk, and eq∈Pk such that eq<Pkei, 0<wi0<wq0, and αi=li, then we have αq=lq.Proof.
Supposeβ=(β1,β2,…,βm) is an optimal solution of the SPIUH-SSCP problem. By Lemma 3, γ=(γ1,γ2,…,γm) defined below is also an optimal solution of the SPIUH-SSCP problem:
(18)γj={lj,ifβj≠wj,wj,ifβj=wj.(1)
If there exists a pathPk, ei∈Pk and eq∈Pk, such that ei<Pkeq, 0<wi0≤wq0, γi=li, and γq=wq, because |Qq|≥|Qi| and reducing the weight of eq first is better, or at least not worse, than reducing that of ei, then we can get that α is also an optimal solution of the SPIUH-SSCP problem, where
(19)αj={wi,ifj=i,lq,ifj=q,γj,otherwise.(2)
If there exists a pathPk, ei∈Pk and eq∈Pk, such that eq<Pkei, 0<wi0<wq0, γi=li, and γq=wq, because by (16) we know that |Qi|=|Qq| and reducing the weight of eq first is better, or at least not worse, than reducing that of ei, then we can get that α is also an optimal solution of the SPIUH-SSCP problem, where
(20)αj={wi,ifj=i,lq,ifj=q,γj,otherwise.Thus repeating the above operations, we can get an optimal solution α of the SPIUH-SSCP problem that satisfies the property in Lemma 10.Theorem 11.
If the SPIUH-SSCP problem is feasible, then Algorithm9 outputs an optimal solution w* of the SPIUH-SSCP problem in O(m(r+logm)) time.Proof.
If the SPIUH-SSCP problem is feasible, then it is not difficult to show that the solutionw* obtained by Algorithm 6 is a feasible solution of the SPIUH-SSCP problem.
Next we show thatw* obtained by Algorithm 9 satisfies properties (1) and (2) in Lemma 10. Note that we run Step 2 of Algorithm 5 for the path Pk by using stable sorting method in the kth iteration of for-loop in Algorithm 9 for any 0≤k≤r. When ei is added to S in the kth iteration of for-loop in Algorithm 9, we consider the following two cases.
(1) If there is aneq satisfying ei<Pkeq and 0<wi0≤wq0, then by the greedy property of Algorithm 9 (i.e., if ei<Pkeq and 0<wi0≤wq0, then eq is added to S before ei is added to S), we have eq∈S. Hence, for any wi*=li (i.e., ei∈S), if ei<Pkeq, 0<wi0≤wq0, then we have wq*=lq (i.e., eq∈S).
(2) If there is aneq∈Pk such that eq<Pkei, 0<wi0<wq0, then by the greedy property of Algorithm 9 (i.e., if eq<Pkei, 0<wi0<wq0, then eq is added to S before ei is added to S), we have eq∈S. Hence, we have wq*=lq.
Hence,w* obtained by Algorithm 9 is a feasible solution of the SPIUH-SSCP problem that satisfies properties (1) and (2) in Lemma 10.
Suppose thatα is the optimal solution of the SPIUH-SSCP problem which satisfies the property (1) and (2) in Lemma 10. Now we show that for each eq∈E, if wq0>0 and wq*=lq, then αq=lq. Suppose wq*=lq (i.e., eq∈S); we consider the following three cases.
Case  1. If there exist a path Pk and an edge ei∈Pk such that ei<Pkeq, 0<wi0≤wq0, and αi=li, then because the optimal solution α of the SPIUH-SSCP problem satisfies property (1) in Lemma 10, we can get that αq=lq.
Case  2. If there exist a path Pk and an edge ei∈Pk such that eq<Pkei, 0<wi0<wq0, and αi=li, then because the optimal solution α of the SPIUH-SSCP problem satisfies property (2) in Lemma 10, we can get that αq=lq.
Case  3. If for each Pk and for each ei∈Pk such that (1) ei<Pkeq, 0<wi0≤wq0 or (2) eq<Pkei, 0<wi0<wq0, we have αi=wi. Note that wq*=lq (i.e., eq∈S); suppose eq is added to S in the kth iteration of for-loop in Algorithm 9; let Ω={ei∣ei∈Pk,0<wq0<wi0}∪{ei∣ei∈Pk, eq<Pkei,0<wq0=wi0}, Θ=Pk∖Ω={eq}∪Γ, where Γ={ei∣eq<Pkei,0≤wi0<wq0}∪{ei∣ei<Pkeq,0≤wi0≤wq0}; then ∑ei∈Ωli+∑ei∈Θwi>dk (otherwise, eq∉S). Note that we have the assumption that αi=wi for each ei∈Γ, if αq=wq; then
(21)α(Pk)=∑ei∈Ω‍αi+∑ei∈Θ‍αi=∑ei∈Ω‍αi+αq+∑ei∈Γ‍αi=∑ei∈Ω‍αi+wq+∑ei∈Γ‍wi≥∑ei∈Ω‍li+∑ei∈Θ‍wi>dk.
This contradicts that α is an optimal solution of the SPIUH-SSCP problem, so αq=lq.
Hence, for eacheq∈E, if wq0>0 and wq*=lq, then αq=lq. That is, the objective value of w* is not greater than the objective value of α. Note that α is an optimal solution of the SPIUH-SSCP problem, so w* is an optimal solution of the SPIUH-SSCP problem.The time complexity analysis is similar to that of Theorem7.Example 12.
As shown in Figure2(a), let w=(2,3,2,1,2), l=(0,0,0,0,0), and d=(3,3,3). The optimal solution of the SPIUH-SSCP problem generated by Algorithm 9 is w*=(0,0,2,1,2), and the optimal objective value is 2.Remark 13.
Note that Algorithm9 cannot always obtain an optimal solution of the SPIUH-SS problem. For example, as shown in Figure 2(b), let w=(1,1,3,3,3), l=(0,0,0,0,0), and d=(3,3,3). In this case, it is an instance of SPIUH-SS problem, but not an instance of SPIUH-SSCP problem. The solution generated by Algorithm 9 is w*=(1,1,0,0,0), whose objective value is 3. But the optimal solution is α=(0,0,3,3,3), and the optimal objective value is 2.So it is meaningful to design efficient algorithms for the SPIUH-SS problem. We guess that the SPIUH-SS problem has strongly polynomial time algorithms.


## 4. A Heuristic Algorithm for the General SPIUH Problem

In this section, we design a heuristic algorithm to solve the general SPIUH problem (1) and give computational experiments to test effectiveness of the algorithm.Lemma 14 (see [8]).
The SPIUH problem is strongly NP-hard even ifli=0 for each edge of the network.Similar to Lemma2, we can use the next lemma to check the feasibility of SPIUH problem.Lemma 15.
The SPIUH problem (1) is feasible if and only if dl(sk,tk)≤dk, for each k=1,2,…,r.We design a heuristic algorithm to solve the SPIUH problem. The main idea is as follows.Suppose the SPIUH problem is feasible. Initializel′=l. Define K={k∣1≤k≤r,dw(sk,tk)>dk}. First compute a shortest path Pk from sk to tk under l′ for each k∈K. Let X={ei∣ei∈Pk,k∈K} and X′={ei∣ei∈X,wi-li′>0}. Then find a specific edge ej∈X′, and update li′=wj and X′=X′-{ej}. Next we check if the SPIUH problem is feasible or not under the current weight l′. If not, modify lj′ to the original value lj. Repeat the above process until X′=∅. Note that there is an edge deleted from X′ in each iteration and the cardinality of the original set X′ is at most m, and hence the algorithm can be done in m iterations.Algorithm 16.
Consider the following.Input: A network G with a set {(sk,tk)∣k=1,2,…,r} of source-terminal pairs, two edge length vectors l,w and a set {dk∣k=1,2,…,r} of values.Step  1: For each k=1,2,…,r, compute dl(sk,tk) and dw(sk,tk). If there exists a shortest path Pk from sk to tk under l such that l(Pk)>dk, then output that the SPIUH problem has no feasible solution, stop. Otherwise, let l′=l and K={k∣1≤k≤r,dw(sk,tk)>dk}. For each k∈K, compute a shortest path Pk from sk to tk under l′.Step  2: Let X={ei∣ei∈Pk,forak∈K}. For each edge ei∈X, let Qi={Pk∣ei∈Pk,k∈K}. Let X′={ei∣ei∈X,wi-li′>0}.Step  3: While X′≠∅, do
Find the edgeej such that j=argmin{(wi-li′)|Qi|∣ei∈X′}, and let li′=wj and X′=X′∖{ej}.Compute a shortest pathPk from sk to tk under l′ in the set Qj of paths. Call the new path as Pk′, if l′(Pk′)>dk, then li′=lj (and ignore Pk′); otherwise, let Pk=Pk′ (i.e., delete the previous Pk), X={ei∣ei∈Pk,k∈K} and Qi={Pk∣ei∈Pk} for each edge ei∈X.Step  4: Let S={ei∣ei∈X,li′=li,wi≠li}, output an approximation solution w* and its objective value |S| of the SPIUH problem, where
(22)wi*={li,ifei∈S,wi,otherwise.Now we analyze the time complexity of Algorithm 16. For each k=1,2,…,r, there are O(n2) operations to compute a shortest path Pk; and hence there are O(rn2) operations in Step 1, where n=|V|. Step 2 requires O(nm) operations. Step 3 requires O(r2n3) operations. Furthermore, there are at most m iterations in Algorithm 16. Hence Algorithm 16 runs in O(r2n3m) operations in the worst case, and it is a strongly polynomial time heuristic algorithm.Next we first give an example to explain detailed computation process of the heuristic Algorithm16, and then we present its computational experiments.Given is a networkG=(V,E) shown in Figure 3, where V={s1,s2,s3,v1,v2,v3,t1,t2,t3}, E={ei∣i=1,2,…,14}. Let w=(4,3,6,4,5,6,5,4,8,7,6,6,4,7), l=(3,2,5,3,4,3,4,3,6,4,5,4,3,4), the set of source-terminal pairs of vertices is {(sk,tk),k=1,2,3}, and d=(13,14,11).Figure 3
An example of the SPIUH problem.When calling Algorithm16 for the instance given by Figure 3, we obtain an approximation solution w*=(4,3,5,4,5,6,5,3,8,4,6,6,4,4), and its objective value is |S|=4, where
(23)wi*={li,ifei∈S,wi,otherwise.See Table1 for the details of iterations in running Algorithm 16.Table 1
Iteration process of Algorithm16.
IN
P
k
l
′
(
P
k
)
d
k
e
j
LW
IN
P
k
l
′
(
P
k
)
d
k
e
j
LW
1
s
1
s
2
v
1
s
3
t
1
13
13
s
2
v
1
v
3
t
2
10
14
e
1
Yes
6
s
3
t
1
t
2
t
3
12
11
e
8
No
s
3
v
1
v
2
t
3
11
11
2
s
1
v
2
v
1
s
3
t
1
13
13
s
1
t
3
t
2
t
1
13
13
s
2
v
1
v
3
t
2
10
14
e
2
Yes
7
s
2
s
1
t
3
t
2
13
14
e
12
Yes
s
3
v
1
v
2
t
3
11
11
s
3
t
1
t
2
t
3
11
11
3
s
1
t
3
t
2
t
1
14
13
e
3
No
8
s
1
t
3
t
2
t
1
15
13
e
10
No
4
s
1
t
3
t
2
t
1
13
13
s
2
v
1
v
3
t
2
11
14
e
4
Yes
9
s
1
t
3
t
2
t
1
15
13
e
14
No
s
3
v
1
v
2
t
3
11
11
5
s
1
t
3
t
2
t
1
13
13
s
2
v
1
v
3
t
2
11
14
e
5
Yes
s
3
v
1
v
2
t
3
11
11
IN: the number of iterations;ej: edge obtained in step 3; l′(Pk): the distance of the shortest path Pk under l′; LW: can lj′ be changed to wi?Note that when Algorithm16 is applied to solve the SPIUH-SSCP problem, similar to the proof of Theorem 11, it is not difficult to show that Algorithm 16 can obtain an optimal solution of the SPIUH-SSCP problem.The heuristic Algorithm16 is coded in Matlab 7.0 and run on a PC Pentium D, 2.8 GHz, under Windows XP. We have tested the heuristic algorithm on ten classes of network configurations which differ from the number n of nodes, varying from 30 to 100, and the number r of source-terminal pairs, being 5 or 15. There are 50 or 100 random instances generated for each class of network configuration. In all instances of the configurations, the length range of wi is 0–37 for each edge ei, and the length range of lower bound li is 0–15. In order to avoid solving a big number of nonfeasible instances, we assume that dk is between dl(sk,tk) and dw(sk,tk) for each source-terminal pair (sk,tk).Computational results are shown in Table2. It displays the average approximation objective values and the average CPU-time in seconds of Algorithm 16 and implicit enumeration algorithm by using 50 or 100 instances in each class of network configuration. Table 2 shows that the average running time of Algorithm 16 is far less than that of implicit enumeration algorithm, and if m≥50 and optimal objective value is greater than 5, then the running time of implicit enumeration algorithm is unbearable.Table 2
Computational results of the Algorithm16 and that of implicit enumeration algorithm.
NI
n
m
r
VC
VC1
TC
TC1
100
25
35
5
7.5
5.2
0.29
1068.61
100
30
40
5
7.4
5.3
0.53
4687.8
100
35
45
5
7.2
5.7
0.78
8512.14
50
35
50
5
7.6
5.6
0.9
11360.04
50
40
50
10
8.7
—
1.29
—
50
45
70
10
10.2
—
2.6
—
50
100
130
15
18.4
—
49.4
—
50
100
150
15
18.1
—
283.4
—
50
150
200
15
39.9
—
296
—
50
200
250
30
52.4
—
789.8
—
NI: the number of instances;n: the number of nodes; m: the number of edges; r: the number of source-terminal pairs; VC: average approximation objective value by using Algorithm 16; VC1: average objective value by using implicit enumeration algorithm; TC: average running time in CPU-seconds by using Algorithm 16; TC1: average running time in CPU-seconds by using implicit enumeration algorithm.


## 5. Conclusion and Further Research

The shortest path improvement problems under unit Hamming distance are studied. Firstly, the problem on arborescent networks is formulated as a 0-1 integer programming model. Secondly, two greedy algorithms are proposed for problems on chain networks and special star-tree networks. Thirdly, a strongly polynomial time algorithm is designed for the problem on arborescent networks with a single source and a special constraint on paths. Finally, a heuristic algorithm and corresponding computational experiments are presented for the SPIUH problem on general graphs.For further research, it is meaningful to design exact algorithms or approximate algorithms for the shortest path improvement problems on arborescent networks with a single source under unit Hamming distance and to propose approximate or heuristic algorithms for the shortest path improvement problems under general Hamming distance.



---

*Source: 847317-2013-09-26.xml*