IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 50 (2012), 1180 ISSN 2232-2094 STACKELBERG SHORTEST PATH TREE GAME, REVISITED Sergio Cabello Ljubljana, July 11, 2012 1—1 Stackelberg Shortest Path Tree Game, Revisited Sergio Cabello^ July 10, 2012 o 00 ¡5 CO CO CD CO Abstract Let G(V, E) be a directed graph with n vertices and m edges. The edges E of G are divided into two types: Ep and EP. Each edge of Ep has a fixed price. The edges of EP are the priceable edges and their price is not fixed a priori. Let r be a vertex of G. For an assignment of prices to the edges of EP, the revenue is given by the following procedure: select a shortest path tree T from r with respect to the prices (a tree of cheapest paths); the revenue is the sum, over all priceable edges e, of the product of the price of e and the number of vertices below e in T. Assuming that k = |EP | > 2 is a constant, we provide a data structure whose construction takes O(m+n logk-1 n) time and with the property that, when we assign prices to the edges of EP, the revenue can be computed in (logk-1 n). Using our data structure, we save almost a linear factor when computing the optimal strategy in the Stackelberg shortest paths tree game of [D. Bilo and L. Guala and G. Proietti and P. Widmayer. Computational aspects of a 2-Player Stackelberg shortest paths tree game. Proc. WINE 2008]. 00 1 Introduction A Stackelberg game is an extensive game with two players and perfect information in which the first player, the leader, chooses her action and then the second player, the follower, informed of the leader's choice, chooses her action; see [10, Section 6.2]. In a Stackelberg pricing game in networks, the leader owns a subset of the edges in a network and has to choose the price of those edges to maximize its revenue. The other edges of the network have a price already fixed. The follower chooses a subnetwork of minimum price with a prescribed property, like for example being a spanning tree or spanning two vertices. The revenue of the leader is determined by the prices of the edges that the follower uses in its chosen subnetwork, possibly combined with the amount of use of each edge. Stackelberg network pricing games were first studied by Labbe et al [9] when the follower is interested in a cheapest path connecting two given vertices. They showed that even such "simple" problem is NP-hard when the number of priceable edges is not bounded. There has been much follow up research; we refer the reader to the overview by van Hoesel [13]. The case when the follower is interested in a cheapest spanning tree was introduced by Cardinal et al. [7]. Bilo et al. [2] considered the case when the follower is interested in a shortest path tree from a prespecified root r and the revenue of a priceable _ *This work has been partially financed by the Slovenian Reseedgeh Agency, program P1-0297, project J1-4106, and within the EUROCORES Programme EUROGIGA (project GReGAS) of the European Science Foundation. cu ^Department of Mathematics, IMFM, and Department of Mathematics, FMF, University of Ljubljana, Slovenia. email: sergio.cabello@fmf.uni-lj.si edge is the product of its price and the number of times such edge is used by paths from r in the tree. This is the model we will consider. We next provide the formal model in detail and explain our contribution. o The shortest path tree game. We next provide a description of the Stackelberg shortest path tree game. In fact, we present it as an optimization problem, which we denote by StaokSPT. The input consists of the following data: U cu A directed graph G = (V, E) with n vertices and m edges. • A partition of the edges E into Ep U EP. The edges of EP are the priceable edges and the edges of Ep are the fixed-cost edges. • A root r e V(G). 00 • A demand function 0 : V(G) ^ R>0, where 0(v) tells the demand of vertex v. • A cost function c : Ep ^ R>0 fixing the price of the edges in Ep . An example is given in Figure 1. A feasible solution is given by a price function p : EP ^ R>0. The cost function c and the price function p define a weight function wp : E ^ R>0 over all edges by setting wp(e) = p(e) if e e EP and wp(e) = c(e) if e e Ep. This weight function defines shortest paths in G. (In fact, they should be called cheapest paths in this context.) For a price function p and a path n, the revenue per unit along n is (N eGEp n E(n) Pu(n,p) := p(e)- Note that only priceable edges contribute to the revenue. Let T be a subtree of G containing paths from r to all vertices. For any vertex v e V(G), let T[r, v] denote the path in T from r to v. The revenue given by T is p(T,p) := 0(v) ■ pu(T[r, v],p). vev (G) We would like to tell that the revenue given by the price function p is p(T,p), where T is a shortest path tree from r with respect to wp. However, there may be different shortest path trees T with different revenues. In such case, T is taken as the shortest path tree that maximizes the revenue. Although this assumption may seem counterintuitive at first glance, it forces the existence of a maximum and avoids the technicality of attaining revenues arbitrarily close to a value that is not attainable. Thus, the revenue of a price function p is defined as p(p) := max{p(T,p) | T a shortest path tree in G with respect to wp}. (1) m As an optimization problem, StaokSPT consists of finding a price function p such that the revenue p(p) is maximized. From the point of view of game theory, the leader chooses the price function p and the follower chooses a tree T containing paths from r to all vertices. The payoff of the leader is p(T, p). The payoff of the follower is the sum, over all vertices v of G, of the distance in T from r to v. Among trees T with the same payoff for the follower, she maximizes the revenue p(T,p). Thus, the follower uses a lexicographic order where, as primary criteria, lengths are minimized, and, as secondary criteria, revenue is maximized. CM i-H o CM o 00 4 n— -«- c J— 4 3 5 1 2 4 1 _ e3 _, 4 3 1 2 4 4 2 3 1 ei , W_e2 3 1 ( 12 1 1/ 3 1/12 1 ^ 3 3 3 U 1 e4 4 4 3_ T 1 V 2 1 Figure 1: An example of a Stackelberg shortest path tree game. We assume that each vertex has unit demand. 0 o CM 1 CM CO CM CM £ CO CO m CD $h CD m u a CD U Our result and comparison. We assume henceforth that k := |Ep| > 2 is a constant. For k = 1, StaokSPT can be solved in O(m + n logn) time as discussed by Bilo et al [2]. We describe a data structure that can be constructed in O(m + n logk-1 n) time and with the property that, given a price function p, the revenue p(p) can be computed in O(logk-1 n) time. Bilo et al. [2] show how to find an optimal price function p by evaluating the revenue of O(nk) price functions1. Combined with our data structure, we can then find an optimal price function in O(m + nk logk-1 n) time. Our result matches the result of Bilo et al. [2] for the case k = 2. For k > 3, the algorithm of Bilo et al. uses O(nk(m + n logn)) time. A previous algorithm by van Hoesel et al. [14] to compute the optimal solution in a more general Stackelberg pricing problem, where paths from different sources have to be considered, reduces StackSPT to O(n4 ) linear programs of constant size. The large dependency on k is unavoidable because the problem is NP-hard for unbounded k. Inapproximability results were shown by Joret [8], and improved by Briest et al. [4], for the shortest path between two points. This is a special case of our model where the demand function 0 is nonzero for a single vertex. Briest et al. [5] provide an approximation algorithm for more general Stackelberg network pricing games. When it is specialized to StackSPT, it provides a O(logn)-approximation. Our data structure is based on three main ideas: • A careful rule to break ties when there are multiple shortest path trees. With this rule, we can easily split the vertices into groups that use the same priceable edges. • Using a smaller network, of size O(k2), such that, for a given price function, we can find out the structure of the priceable edges in the shortest path tree of the network. This idea is similar to the shortest paths graph model of Bouhtou et al. [3]. • Mapping each vertex of the network to a point in Euclidean k-dimensional space in such a way that the vertices that use a certain subset of the priceable edges can be identified as a subset of points in a certain octant. This allows us to use efficient data structures for range searching. Similar ideas have been used for graphs of bounded treewidth; see [1, 6, 11] and [12, Chapter 4]. 1They only discuss the case when the demand function 0 is identically 1. However, their discussion can be easily adapted to more general demand functions. 1 5 r 2 3 2 Notation. We use e\, e2,..., ek to denote the edges of EP, where each edge ei = .si^ti. The enumeration of the edges is fixed; in fact we will use it to break ties. Perhaps a bit misleading but quite useful, we will use p(e) = 0 for each e e EF. For a subset of vertices U C V(G) we use the notation 0(U) := ^ueu 0(u). For a subset of edges F C E we use the notation wp(F) := wp(e) and p(F) := EeeFP(e) = EeeFnEF P(e). A path n will be treated sometimes as a sequence of vertices and sometimes as an edge set. No confusion can arise from our use. We use EP(n) for the set of priceable edges along n, that is, EP(n) = n n EP. Similarly, we use EF(n) = n n EF for the fixed-cost edges. Therefore wp(EP(n)) = p(n n EP) and wp(EF(n)) = c(n n EF). For any two vertices u and v of G we use np(u, v) to denote a shortest path from u to v with respect to the weights wp and dp(u,v) to denote its weight. We use d0 as a shorthand for dp when p = 0, that is, when the price function assigns price 0 to each priceable edges. We use d^ as a shorthand for dp when p = to, that is, when the price function assigns price to to each priceable edge. For a path n and vertices u, v along n, we use n[u, v] for the subpath of n from u to v. Similarly, as we have used above, for a tree T and vertices u, v, we use T[u, v] to denote the subpath of T from u to v. o I cm 00 cd co 2 Range Searching Let X be a set of points in R . Assume we are given a function ^ : X ^ R that assigns a weight <^(x) to each point x e X. We extend the weight function to any subset Y of CM points by <^(Y) := ^xeY <^(x). A rectangle R in R is the Cartesian product of d intervals, R = I\ x ■ ■ ■ x Id, where each interval Ii can include both extremes, one of them, or none. Orthogonal range searching deals with the problem of preprocessing X such that, for a query rectangle R, certain properties of X n R can be efficiently reported. We will use 2 the following standard result. Theorem 1 ([15]). Let d > 2 be a constant. Given a set of n points X c Rd and a weight function p : X ^ R, there is a data structure that can be constructed in O(n logd-1 n) time such that, for any query rectangle R, the weight p(X n R) can be reported in time. 3 Breaking Ties Evaluating the revenue of a price function is easier in a generic case, when there is a unique shortest path from r to each vertex of V(G). In contrast, in the degenerate case, there is at least one vertex v with two distinct shortest paths from r to v. Unfortunately, the price functions defining the optimum are degenerate. This is easy to see because, in a generic case, a slight increase in the price function leads to a slight increase in the revenue. In our approach, we will count how many vertices use a given sequence of priceable edges. For this to work, we need a systematic way to break ties, that is, a rule to select, among the shortest path trees that give the same revenue, one. We actually do not go that far, and only care about the priceable edges on the paths of the tree. We first discuss how to break ties among shortest paths, and then discuss how to break ties among shortest path trees. Essentially, we compare paths lexicographically according to the following: firstly, we compare paths by length; secondly, if they have the same length, we compare them by revenue; finally, if they have the same length and revenue, we compare the priceable edges on the path lexicographically, giving preference to priceable edges of larger index. We next provide the details. Define the function x : E ^ R>0 by x(ej) := 2l, when e% G EP, and x(e) := 0 when e G EF . We extend the function to subsets of edges by defining CM o I cm 00 VF C E : x(F):=£ x(e) = ^ 2* e£F ei£F Note that, for any two subsets F and F' of priceable edges, x(F) > x(F') if and only if the edge with largest index in the symmetric difference of F and F' comes from F. Moreover VF, F' C Ep : x(F) = x(F') ^ F = F'. (2) Define the function o wp : E ^ R>0 x R<0 x R>0 e ^ (wp(e), -p(e), -x(e)) Recall that we had set p(e) = 0 when e G EF. We extend Wp to subsets of edges by setting VF C E : Wp(F) := ^ Wp(e). e€F We treat Wp as composite weights that are compared using the lexicographic order —. We say that a path n is Wp-shorter than a path n' if and only if Wp(n) — Wp(n'), where — denotes the lexicographic order. For any cycle a, the first component of Wp(a) is wp(a), which is positive. This implies that we do not have "negative cycles" and we can use the weights Wp to define Wp-shortest paths: a path n from u to v is wp-shortest if Wp(n) is minimal, among the paths from u to v, with respect —. More compactly: n from u to v is Wp-shortest ^^ V paths n' from u to v : Wp(n) ^ Wp(n'). A tree T is a wp-shortest path tree (from r) if it contains a wp-shortest path from r to each vertex. Note that this is stronger than telling that wp(E(T)) is minimal with respect to —. See Figure 2 for an example. A Wp-shortest path tree can be computed be computed in O(m + n log n) time using Dijkstra's algorithm with the weights Wp and lexicographic comparison2. (Here we need that k is a constant, which implies that x(F) uses k = O(1) bits. For general k, the running time of Dijkstra's algorithm may get an additional dependence on k, depending on the model of computation.) Note that there may be several Wp-shortest path trees because of different shortest paths without priceable edges. Lemma 2. If T be a wp-shortest path tree, then p(T,p) = p(p). CD Proof. Since T is a wp-shortest path tree, it is also a shortest path tree for the weights wp. By the definition of p(p) given in equation (1), we have p(T,p) < p(p). We next show that p(T,p) > p(p), which implies that p(T,p) = p(p). Consider a shortest path tree T* that defines the value p(p). That is, p(T*,p) = p(p). Since T is a Wp-shortest path tree, we have cd Vv G V(G) : Wp(T[r,v]) ^ Wp(T*[r,v]). (3) CU 2If one dislikes using lexicographic comparison, it is also possible to use weights w' (e) = w(e) — eip(e) — £2x(e), where e1 = maxe w(e)/n3 and e2 = e1/(2fcn3). CM i-H o CM o 00 0 o CM 1 CM CO CM CM £ CO CO 1 4 5 4 9 4 13 5 18 »o » - » — 4 3 5 , I4 1 _ 5 3 4 4 4 8 4 ^12 4 16 31 1 3 4 3 4 10 ♦ 1 2 ♦ 3 1/12/11 1 3 1 2 10 12 1 Figure 2: A wp-shortest path tree for the price function p(ei) = 3, p(e2) = p(e4) = 4, p(e3) = 1 in the network of Figure 1. The values in the vertices are the distance from r. Note that there are some vertices, like for example the two that are marked with squares, for which there are different shortest paths using different priceable edges, so we have to select shortest paths maximizing revenue. The revenue given by this tree, if each vertex has unit demand, is p(e1) ■ 10 + (p(e1) + p(e2)) ■ 2 + p(e3) ■ 2 = 46 units. Since T and T* are both shortest path trees, we have Vv e V(G) : wp(T[r,v]) = wp(T*[r,v]). Expanding the definition of wp, from (3) and (4) we obtain Vv e V(G) : p(T[r,v]) > p(T*[r,v]). This means that p(p) = p(T*,p) = £ 0(v) ■ p(T*[r, v]) < ^ 0(v) ■ p(T[r,v]) = p(T,p). vev(o) vev (G) (4) □ m CD CD m u a CD U cu 4 Reduced trees and sequences of priceable edges Consider a price function p. Let T be a wp-shortest path tree from r. The wp-reduced tree RT is obtained from T by contracting all the fixed-cost edges Ep n E(T). The resulting graph is a tree with edge set EP n E(T). When considering RT, we disregard the prices p and the orientation of the edges, and consider it as a rooted, unweighted, undirected graph with distinct labels e1;..., ek on its edges. In general, we will use RH to denote the reduced graph obtained from a graph H by contracting all non-priceable edges. The wp-reduced tree for the example of Figure 2 contains the edges e1 and e3 adjacent to r and the edge e2 below e1. We first show that the wp-reduced trees are independent of the wp-shortest path tree that is used. Lemma 3. If T and T1 are wp-shortest path trees, then RT = RT'. r 3 2 2 2 2 3 1 1 6 1 2 3 2 9 i-H o o 00 0 o 1 CO ^ CO CO CO CD $H CD CO $H a CD $H Figure 3: Left: The model graph for the network of Figure 1. Edges with infinite weight, like for example r^t4 or t^t2, are not drawn. Right: the Wp-shortest path tree in the model for the price function of Figure 2: p(e1) = 3, p(e2) = p(e4) = 4, and p(e3) = 1. Proof. Since both T and T' are wp-shortest path trees we have Vv e V(G) : wp(T[r,v]) = wp(T'[r,v]), which means Vv e V(G) : Wp(T[r,v]) = wp(T'[r,v]), p(T [r,v]) = p(T' [r,v])), X(T [r,v]) = x(T '[r,v]). From the last equality and the property (2) we have Vv e V(G) : Ep(T[r,v]) = Ep(T'[r,v]). If ej = Si^ti is a descendant of ej in T, this means that ej e EP(T[r, Sj]) and ej e Ep(T[r,tj]). But then for T' we also have ej e Ep(T'[r,Sj]) and ej e Ep(T'[r,tj]), which implies that ei is a descendant of ej in T'. By symmetry, we conclude that ei is a descendant of ej in T if and only if ei is a descendant of ej in T'. This implies that the Wp-reduced trees RT and RT' are the same. □ A useful consequence of this is that any two wp-shortest path trees have the same subset of priceable edges. Lemma 4. In O(m + n logn) time we can construct a data structure with the property that, for any given price function p, we can compute in O(1) time the wp-reduced tree RT. Proof. We construct the model graph G = G(G,Ep, c, r), as follows. The vertex set of (5 consists of r and the endpoints of the priceable edges. Thus V((G) = {r} U {s1, t1,..., sk,tk}. In G, we have edges from r to any other vertex. Furthermore, for each priceable edges ei and ej, i = j, we have an edge from ti to Sj and to tj. Finally, we have the edges e1,..., ek themselves. Each edge u^v in E(G) that is not a priceable edge gets weight v). That is, each edge u^v gets weight equal to the distance between u and v in G — Ep . This finishes the description of the model graph G. See Figure 3, left, for an example. This construction is similar to and inspired by the shortest paths graph model of Bouhtou et al. [3]. r r The model graph G has the same priceable edges as G. Consider any price function p. We claim that the wp-reduced trees for G and G are the same. That is, if T denotes a wp-shortest path tree in G and RT denotes the wp-reduced tree obtained after contracting all non-priceable edges, then RT = RT. See Figure 3, right, for an example. Consider the subgraph F of G obtained by "expanding" each shortest path of T: for each priceable edge e» in T we put the same edge in F; for each non-priceable edge u^v of T we put in F a shortest path of G — Ep that connects u to v. The graph F is like a wp-shortest path forest spanning the vertices of V(G). Any path in T corresponds to a path in F with the same composite weight wp. The reduced tree RT is obtained from F by contracting the fixed-cost edges E(F) n EF. That is, RF = RT. Consider any edge e» e Ep. Since T[r, t»] is a wp-shortest path in G, we have Wp(T[r,ti]) X Wp(F[r,tj]). O - - Since T[r, t»] is a wp-shortest path in G, we have Wp(T[r,tj]) = Wp(F[r,tj]) X Wp(T[r,t*]). We thus conclude that Wp(T [r,tj]) = Wp(F [r,tj]). This means that X(T [r,tj]) = x(F [r,tj]), and by (2) we get that Ep (T [r,tj]) = Ep (F [r,tj]) = Ep (T [r,t*]). CM The same discussion for s» implies that Ep (T [r,sj]) = Ep (F [r,sj]) = Ep (T [r,Sj]). Since the same holds for each priceable edge e», it follows that RT and RT. Indeed, if CM ej is a descendant of e», then ej e Ep(T[r, s»]) and ej e Ep(T[r, t»]), which means that ej e Ep(T[r, Sj]) and ej e Ep(T[r, t»]), and we conclude that e» is a descendant of ej in T. This finishes the proof of the claim. Since RT = RT and RT can be computed in constant time because G has constant size, the result follows. □ Let T be the family of all possible reduced trees, over all possible graphs G. Thus T is the family of rooted trees with at most k edges where each edge has a distinct label among ei,..., ek. It is clear that the number of such trees depends only on k, and thus it is bounded by a constant in our case. Consider any reduced tree R e T. Each edge e» that appears in R defines a sequence of priceable edges, denoted by a(e», R), which is the sequence of edges followed by the path in R from the root to e». The edge e» is the last edge of a(e», R). When e» is not in R we define a(e», R) as the empty sequence. Since each edge of R defines a different sequence of edges, the tree R e T defines |E(R)| nonempty sequences. For any nonempty sequence a = (e»1,..., e^) of distinct priceable edges, we define W»(a) := d^(r,s»i)+ ^ d»^, Sj+i), 1- (p(a'), x(a')), where >-denotes the lexicographic comparison. Therefore O a a' ^^ p(a) > p(a') or (p(a) = p(a') and x(a) > x(a')) S CO CO CD CO CD U Because of property (2), 2 is a constant. Consider a reduced tree R e T and an edge ei e E(R). In time O(m + n logk-1 n) we can construct a data structure with the following property: given a price function p with the property that its wp-reduced tree is R, we can obtain 0(V(ei;p)) in O(logk-1 n) time. Proof. For each vertex v e V(G) we define a point pv e Rk whose jth coordinate is CD p (j):=i W~(^(ei,R)) + (ti,v) - W^(a(ej, R)) - ,v) if j = i; l W^(a(ei, R)) + d^(ti, v) - d^(r, v) if j = i. Let P be the set of points | v G V(G)}. To each point G P we assign the weight ) := 0(v). We then store the point set P using the data structure for range searching of Theorem 1. This finishes the description of the data structure. The construction of the data structure takes O(m + n logk-1 n) time. We first run a shortest path tree algorithm in G — Ep from r and from each endpoint of the edges in Ep. This takes O(k(m + n log n)) = O(m + n log n) time. With this information we can obtain each coordinate of each point in constant time, and thus we construct P in O(n) time. The construction of the data structure of Theorem 1 takes O(n logk-1 n) time because we have k-dimensional points. Consider a price function p and let T be a -Sp-shortest path tree. By assumption, RT = R. We next explain how to recover 0(V(e^p)). For every j = 1,..., k, define the interval O 00 o Gï u cu , R)) — p(a(ej,R))] if i = j and a(ej,R) -

,P(o-(ej, R)) — p(a(ei;R))) if i = j and a(ei;R) a(ej,R); -p(a(ei,R))j if i = j. Consider a vertex v G V(G). The path T[r, v] can be disjoint from Ep or follow one of the sequences a(ei, R),..., a(ek, R). Using the relation in equation (5), we see that the path T[r, v] follows the sequence a(ej, R) if and only if the following conditions hold: wp(T[r,ti]) + d^(ij,v) < dœ(r, v), Vj = i, a(ej, R) a(ej, R) : Wp(T[r,ti])+ d^(ii,v) < Wp(T[r,j]) + ,v); Vj = i, a(ei, R) ^p a(ej, R) : Wp(T[r,ti])+ d^(ii,v) < Wp(T[r,j]) + ,v). 'pl^ L' ; HJ; ^ H; ^ ^ u-'pv^ L' > jJ/ ^ "^v j Because of equation (6), we have, for each j = 1,..., k, Wp(T [r,tj]) = p(a(ej ,R)) + ,R)). and thus the conditions are equivalent to: p(a(ei,R)) + Wœ(a(ei, R)) + dœ(ij,v) < dM(r,v), Vj = i, a(ej, R) ^p a(ej, R) : p(ff(e,,R)) + Wœ(a(ei,R)) + d^fev) < p(a(ej,R)) + Wœ(a(ej, R)) + d^(tj,v); Vj = i,a(et,R) ^p a(ej, R) : p(ff(e,,R)) + Wœ(a(ei,R)) + d^(i,,v) < p(a(ej,R)) + Wœ(a(ej, R)) + d^(ij,v). Reordering, we obtain that v G V(e^p) if and only if W^(a(ei,R))+ d^(ij,v) - d^(r,v) < -p(a(ej,R)), Vj = i, a(ej, R) ^p a(ej, R) : W^(a(ei,R)) + d^(ii,v) - W^(a(ej,R)) - d^(ij,v) < p(a(ej,R)) - p(a(ei,R)); Vj = i,a(ei,R) ^p a(ej, R) : Wœ(a(ei,R)) + d^(ii,v) - Wœ(a(ej,R)) - d^(ij,v) < p(a(ej,R)) - p(a(ei,R)). CD This condition is equivalent to for j = 1,...,k : ppv(j) G 1 (j). We conclude that v G V (e»,p) if and only if pv G Hj I (j). We can then recover 0(V (ej, p)) = ^ ^P H Hj I (j)) by querying the data structure for ^ ^P fl H I (j)). Given a price function p, we can compute the values p(a(ej, R)), for j = 1,..., k, in O(1) time. With this information we can compute the extremes of the intervals I(j) and query the data structure for range searching in O(logk-1 n) time. □ Theorem 8. Assume that k > 2 is a constant. Consider an instance to StackSPT with n vertices, m edges, and k priceable edges. In time O(m + n logk-1 n) we can construct a data structure with the following property: given a price function p, the revenue p(p) can be obtained in O(logk-1 n) time. CM o 00 0 Ö o CM 1 u Proof. We start constructing the data structure of Lemma 4, so that we can quickly compute the Wp-reduced tree for any given price function. For each reduced tree R G T and each priceable edge ej G E(R) we construct the data structure from Lemma 7 and denote it by DS(R, ej). This finishes the construction of the data structure. The time bound follows from the time bounds of Lemmas 4 and 7. Consider a price function p. Because of Lemma 6, we have P(P) = E P(a(ei, R)) • <(V(ej,p)). eieE(R) The data to apply this formula can be recovered from the data structures. Firstly, we use the data structure of Lemma 4 to compute the Wp-reduced tree R for p. For each ej G E(R), we query DS(R, ej) to recover <(V(ej;p)). Finally, we compute p(a(ej, R)) for each ej G E(R). Overall, we use O(1) queries to the data structures and each such query takes O(logk-1 n) time. The result follows. □ Corollary 9. Let k > 2 be a constant. The problem StackSPT with n vertices, m edges, and k priceable edges can be solved in O(m + nk logk-1 n) time. Proof. As discussed in the introduction, Bilo et al. [2] show how to solve StackSPT by finding the revenue of O(nk) price functions. Using the theorem we, can find the revenue for all those price functions in O(nk logk-1 n) time after O(m + n logk-1 n) preprocessing time. □ References CO [1] B. Ben-Moshe, B. K. Bhattacharya, and Q. Shi. Efficient algorithms for the weighted 2-center problem in a cactus graph. In X. Deng and D. Du, editors, Proc. ISAAC 2005, volume 3827 of LNCS, pages 693-703. Springer, 2005. [2] D. Bilo, L. Guala, G. Proietti, and P. Widmayer. Computational aspects of a 2-player Stackelberg shortest paths tree game. In Proc. WINE 2008, volume 5385 of LNCS, pages 251-262. Springer, 2008. [3] M. Bouhtou, S. P. M. van Hoesel, A. F. van der Kraaij, and J.-L. Lutton. Tariff optimization in networks. INFORMS Journal on Computing, 19(3):458-469, 2007. • ^ [4] P. Briest, P. Chalermsook, S. Khanna, B. Laekhanukit, and D. Nanongkai. Improved hardness of approximation for Stackelberg shortest-path pricing. In WINE 2010, volume 6484 of LNCS, pages 444-454. Springer, 2010. [5] P. Briest, M. Hoefer, and P. Krysta. Stackelberg network pricing games. Algorith-mica, 62(3-4):733-753, 2012. CD [6] S. Cabello and C. Knauer. Algorithms for graphs of bounded treewidth via orthogonal cu range searching. Computational Geometry: Theory and Applications, 42(9):815-824, 2009. [7] J. Cardinal, E. D. Demaine, S. Fiorini, G. Joret, S. Langerman, I. Newman, and O. Weimann. The Stackelberg minimum spanning tree game. Algorithmica, 59(2):129-144, 2011. O [8] G. Joret. Stackelberg network pricing is hard to approximate. Networks, 57(2):117-120, 2011. [9] M. Labbe, P. Marcotte, and G. Savard. A bilevel model of taxation and its application to optimal highway pricing. Management Science, 44:1608-1622, 1998. [10] M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994. [11] Q. Shi. Single facility location problems in partial k-trees, 2005. Poster at MITACS, Canada. 00 [12] Q. Shi. Efficient Algorithms for Network Center/Covering Location Optimization Problems. PhD thesis, School of Computing Science, Simon Fraser University, 2008. [13] S. P. M. van Hoesel. An overview of Stackelberg pricing in networks. European Journal of Operational Research, 189(3):1393-1402, 2008. [14] S. P. M. van Hoesel, A. F. van der Kraaij, C. Mannino, M. Bouhtou, and G. Ori-olo. Polynomial cases of the tarification problem. Research Memoranda RM03063, Maastricht University, METEOR, 2003. [15] D. E. Willard. New data structures for orthogonal range queries. SIAM J. Comput., 14:232-253, 1985. CO CD $H CD CO u a CD U