in terms of the original input, with the same error bound, but may be exponential in terms of 1/ . Thus, error re-

duction can be exponentially costly for a PTAS, but not for an FPTAS.

432 ALGORITHMIC CHALLENGES IN AD HOC NETWORKS

Example 2: Minimum Energy Path. Let F contain each directed edge in a directed

graph with multiplicity 2, as well as each pair of directed edges that have a common

tail, with multiplicity 1. That is, the two-element edge set {e, f } is in F if and only if

e = (u, v) and f = (u, w) for some vertices u, v, w; v w. It is not difficult to see that

in this case F(P) is precisely the metric that we used in the minimum energy path

problem, in the special case when transmission and reception both need unit energy.

By changing the multiplicities in F, one can incorporate different transmit and re-

ceive energy levels.

Example 3: Minimum Weight k-hop Path. For arbitrary nonnegative integers wi, let F

contain wi copies of edge ei for i = 1, . . . , m, where m is the number of edges. Fur-

ther, for a given integer 1 k m, let F also contain all edge sets H that have the

following properties: |H| = m “ k and the complement of H is a u“v path. Each such

edge set H is included in F with multiplicity M = 1 + m wi. i=1

Now we can observe that the singleton sets in F will contribute w(P) to F(P),

where w(P) is the weight of the path P with edge weights wi. The edge sets of cardi-

nality m “ k in F behave such that if the path has more than k edges, then it intersects

every such set (since each misses only k edges). On the other hand, if the path has

exactly k edges, then precisely one of the different m “ k-element sets is disjoint

from P, the one that has P as its complement. Finally, if P has less than k edges, then

it again intersects all these sets. To see this, observe that a simple u“v path cannot be

a proper subset of another simple u“v path (this claim will be formally proven in the

proof of Theorem 1 below). Therefore, for any set H F, the path P cannot be fully

contained in the complement of H, so P H 0 must hold. Thus, if the number of

/

k-hop u“v paths is denoted by R, then we have

w(P) + RM if |P| k

F(P) =

w(P) + (R “ 1)M if |P| = k

Since M is chosen such that M > w(P) holds for every path, therefore, the path for

which F(P) is minimum will be precisely the one that has minimum weight w(P)

among the u“v paths that have exactly k edges, if such a path exists. If no such path

exists, then F(P) > RM.

(Excercise: Modify the above construction such that the path that minimizes F(P)

will be a minimum weight path among those paths that have at most k edges, if such

a path exists.)

Example 4: Disjoint Connecting Paths with Minimum Total Hops. Let us consider the

following problem of finding multiple paths. Assume that two source nodes s1 and

s2, and two terminal nodes t1 and t2 are given in a directed graph. We would like to

find two edge-disjoint directed paths P1 and P2 such that P1 connects s1 to t1 and P2

connects s2 to t2 and |P1| + |P2| is minimum. The problem is known to be NP-hard. In

fact, just to decide if it is possible to connect the given terminals by edge-disjoint di-

rected paths, irrespective of their lengths, is already NP-complete4 [10]. On the oth-

er hand, as shown in [15], if the paths exist and the objective is to minimize the

4

It is essential that the terminals of each path are specified. If we just look for two edge-disjoint paths to connect

the sets {s1, s2} and {t1, t2}, then it can be solved by network flow techniques in polynomial time.

433

16.3 A UNIFIED REPRESENTATION OF PATH METRICS

length of the longer path, rather than the sum, then it can be approximated in poly-

nomial time within a factor of 2. This also implies an approximation factor of at

most 2 for the summed length, due to max{|P1|, |P2|} < |P1| + |P2| 2 max{|P1|,

|P2|}.

Let us express the problem with the F-measure, for the |P1| + |P2| min objec-

tive. First, if the graph does not contain the edge (t1, s2), then let us add this edge.

Now construct F as follows. Add each edge, except (t1, s2), as a singleton set to F.

Further, let H be the set of s1“t2 paths that contain the edge (t1, s2). For each path P

H let us add the set P (the complement of P) to F with multiplicity m, where m is

the number of edges in the original graph. Every simple path P H is of the form P

= P1(t1, s2)P2, that is, the concatenation of three paths: P1 from s1 to t1, the edge (t1,

s2), as well as another disjoint path P2 from s2 to t2. It is not difficult to see (exer-

cise!) that for such a P

F(P) = |P1| + |P2| + m(|H | “ 1) m|H |

H we have F (P) > m|H |. Thus, the F-shortest path

holds, whereas in case of P

will correspond to the required pair of disjoint paths with the minimum sum of hop

counts.

Having seen some examples, the reader may start wondering: what are the limits of

the expressive power of the F-measure? Can every path metric be expressed in this uni-

fied way by picking the appropriate family of sets for F ? Below, we show that essen-

tially every path metric, no matter how complicated, can be represented this way. Thus,

the F-measure can serve as a canonical representation of all path metrics and, therefore,

the concept of F-shortest path is a canonical representation of any path-optimization

task.

Before going into the representation, let us note that the F-measure, by definition, can

only be a nonnegative integer. As remarked after Definition 1, the model can be directly

extended to the real-valued case. On the other hand, when we search for a u“v path that is

optimal for some path metric h(P) in a graph, the order relationship between the paths

does not change if the metric h(P) is replaced by a + bh(P) for any constants a, b, with b >

0. This implies that, from the path-optimization point of view, it is enough to restrict our-

selves to positive integer valued metrics. That is why we stay with integer multiplicities in

this introductory exposition.

Now we can state the main representation theorem that shows that the F-measure pro-

vides a realization of any integer-valued metric, apart from a constant translation.

Theorem 1 (Path Metric Representation Theorem). Let G be a (directed or undirected)

graph with two distinguished vertices u and v that serve as endpoints of the considered

paths. Let h be an arbitrary path metric that assigns a positive integer value h(P) to every

u“v path P in G. Then there exists a family F of sets of edges in G and a constant M, such

that the F-measure represents the path metric h(P) for every u“v path in G, up to constant

translation, that is,

F (P) = h(P) + M

holds for every u“v path in G.

434 ALGORITHMIC CHALLENGES IN AD HOC NETWORKS

Proof. Let Pu,v be the set of u“v paths in G and let R = |Pu,v|. Set

A= h(P)

P Pu,v

Construct the family F of edge sets as follows. For each P Pu,v include the edge set P

(the complement of P) in F with multiplicity A “ h(P). Define the constant M as

M = (R “ 2)A

We claim that with this choice of F and M the relationship F (P) = h(P) + M holds for

every u“v path in G.

First we show that a simple u“v path P be can never be a proper subset of another sim-

ple u“v path Q. Assume indirectly that P Q, but P Q. Let us traverse Q from u to v.

(Note that if G is undirected, then it is not a priori necessary that the common edges of P,

Q are traversed in the same direction by both paths.) In the traversal of Q, let e be the first

edge in Q that is not contained in P (such an edge must exist, since P is assumed to be a

proper subset of Q). Let w be the endpoint of e that is reached first in the traversal. Then w

v, since Q is not fully traversed yet when we reach w. Now we have two possibilites. (1)

If w = u, then P must leave u on an edge f e. But then, since Q does not visit u again, f

Q must hold, a contradiction to P Q. (2) If w u, then let f1 be the edge on which P

arrives at w and f2 be the edge on which it leaves. Since e P, therefore, f1, f2 e. But

then at least one of f1, f2 cannot be in Q, since Q cannot contain three edges that are inci-

dent to w, so we again contradict P Q. Thus, in either case we arrive at a contradiction,

proving that an u“v path cannot be a proper subset of another one.

Now let us compute F (P) for an arbitrary P Pu,v. By the construction, the sets in F

are all of the form Q with Q Pu,v. Observe that whenever P Q, we have P Q 0, as /

we have shown that in case of P Q the relationship P Q cannot hold, since then P

would be a proper subset of Q. Therefore, if P Q holds, then P must intersect the com-

plement of Q. On the other hand, naturally, P P = 0. Thus, P intersects all sets in F, ex-

/

cept the ones that correspond to its own complement. This implies, by the construction of

F and the multiplicities,

F (P) = [A “ h(Q)] = (R “ 1)A “ h(Q)

Q Pu,v“{P} Q Pu,v“{P}

Observing that the second sum is equal to A “ h(P), we obtain

F (P) = (R “ 1)A “ [A “ h(P)] = h(P) + (R “ 2)A = h(P) + M

í

which proves the theorem.

One can observe at this point that the representation provided in the proof of Theorem 1

generally uses exponentially many different sets for F. This is the case even if a much small-

er F would do, such as for the hop metric in Example 1. Clearly, it would be desirable to

have a “small” representation whenever possible. This points to the first open question.

Open Problem 1. Characterize the path metrics that can be represented by F-measures

that have only polynomially many different sets in F. Find a general method for construct-

ing this “small” representation, whenever it exists.

435

16.4 FINDING THE F-SHORTEST PATH

FINDING THE F -SHORTEST PATH

16.4

Some of the path metrics generate NP-hard path-optimization tasks. For example, as men-

tioned in Section 16.2, the shortest weight constrained path problem has this property.

Since, as we have seen in Section 16.3, the F -measure can represent any path metric,

therefore, we cannot expect that a polynomial-time algorithm exists to find an F -shortest

path for an arbitrary F. On the other hand, we show that it is possible to find an approxi-

mately F -shortest path efficiently, if F is “small.”

Theorem 2. Let F be a family of sets, given by explicit listing, in a (directed or undirect-

ed) graph with n vertices. Assume there are k sets in F (counted with multiplicity), each

with cardinality at most r. Then there is an algorithm of complexity O(max{n2, kr}) that

finds a path P between any two given vertices such that P is an r-approximation of the F -

shortest path, that is,

F (P) rF (P0)

holds, where P0 is an F -shortest path between the same end nodes.

Proof. Let e1, e2 . . . be the edges of the graph and u, v be the end vertices of the sought

path. Let us define edge weights, as follows. To edge ei assign the weight

wi = m(H)

ei H F

where m(H) is the multiplicity of the set H in F. In other words, wi is the number of sets in

F, counted with multiplicity, that contain the edge ei. Each wi can be found and recorded

in altogether O(max{n2, kr}) time, by simply scanning all sets in F and recording for each

edge in how many sets it occured. Now find a minimum weight u“v path P according to

this weighting. Since the path can be found in O(n2) time by Dijsktra™s algorithm, there-

fore, the overall complexity remains O(max{n2, kr}).

Now we claim that the found path P has the desired property of being an r-approxi-

mation of the F-shortest path. Let P0 be an F -shortest u“v path. Let us count for each

edge ei P0 the number of sets H F, counted with multiplicity, that contain ei. Then

we get precisely wi. If we sum up the wi weights along the path P0, then we can get

F can be counted at most r times, as it contains at

at most rF (P0), since each set H

most r edges. On the other hand, this sum is exactly the weight w(P0) under the weight-

ing wi. Thus, we have w(P0) rF (P0). Now observe that the path P, found as a mini-

mum weight path under the weighting wi, cannot have larger weight than any other u“v

path. Therefore, w(P) w(P0) must hold, which implies the desired relationship F (P)

í

rF (P0).

Note that in the above proof we did not really require that the sets of F were explicitely

listed; this was only assumed for simplicity. In fact, it is enough if we have a subroutine

that can count for each edge the number of sets in F that contain the edge.

Regarding the algorithmic issues on F-shortest paths, two open problems are definitely

worth mentioning.

436 ALGORITHMIC CHALLENGES IN AD HOC NETWORKS

Open Problem 2. Characterize the families (or find special families) F of edge sets for

which it is possible to find an F -shortest path in polynomial time.

Open Problem 3. In the case when no polynomial-time algorithm is available to com-

pute an exact solution, find efficient approximations with provable bounds on the

approximation error. An example in this direction is Theorem 2.

16.5 MOBILE PATHS

A proposed method for the assessment and comparison of routing protocols in mobile ad

hoc networks is the MERIT framework [6, 7]. This method compares the route sequences

found by a given routing protocol with an ideal route sequence that could be found if we

knew the node movement in advance. We do not discuss the details of the entire protocol

assessment framework here, as it is covered by [6, 7]. We only consider the interesting

graph algorithmic issues from this framework and point out that they also fit as a special

case in the F -shortest path model.

To model mobility, the MERIT framework introduces the concepts of mobile graph and

mobile path. A mobile graph G is defined as a sequence Gi, i = 1, . . . , T, of graphs on the

same node set, where the successive graphs represent a history of the network topology

changes over some time horizon T:

G = G1G2 . . . GT

In a mobile graph, a mobile path between a source“destination s“t pair is defined as a se-

quence of paths

P = P1P2 . . . PT

where Pi is a static path in Gi between the same source“destination s“t pair.

The weight of a mobile path w(P) includes two basic components:

1. The weights wi(Pi) of the individual static paths, according to arbitrary individual

weightings in the graphs Gi

2. Some transition cost ctrans(Pi, Pi+1) incurred by the protocol whenever there is a

change in the path sequence

Thus, the weight (cost) of a mobile path P is defined as

T T“1

w(P) = wi(Pi) + ctrans(Pi, Pi+1) (16.1)

i=1 i=1

The transition cost between paths is a cost function associated with having to update from

one path to another in the routing protocol. In general, it is the overhead associated with

updating the routing state to reflect the change in the path.

Now we can define the shortest mobile path problem as follows.