We compute for every u in linear time and we set the price of a priceable edge to . Since priceable edges are all forward edges w.r.t. the fixed-cost path, it is easy to see that in any pricing we have that for every priceable edge the distance from u to v is upper bounded by . This implies that the maximum revenue obtainable from is at most . As a consequence, we have that the revenue we can obtain from priceable edges entering in the same node v is at most . Now, the claim follows from the fact that in the distance between any two nodes is equal to the distance in between the same nodes, and hence for every node v which is the head of at least one priceable edge, we obtain revenue . □
The reduction is again from SCP. Given an instance of SCP we build the following instance of the ASSPT game. We have the root vertex r, a node for each , and a node for each . Moreover, let N be an integer that we will fix later. We have additional nodes , , and nodes , .
The fixed-cost edges have all cost 1 and form a path (spanning all nodes) from r to . The sequence of the nodes encountered when we traverse the path from r to is the following: .
The set P
of priceable edges is partitioned into two sets, say
is defined as follows: we have an edge
for each i
, and an edge
for each i
and each j
is defined similarly as in the reduction of Theorem 5, i.e., it contains an edge
and an edge
if and only if
(see Figure 6
). We have the following:
In any optimal pricing p for the instance of the ASSPT game, we have and , for each , and each , when .
Let p be an optimal pricing for and assume by contradiction that the lemma is false. Let i be the minimum index for which the property of the lemma does not hold. Let be the set of priceable edges entering in some , and let . The idea is to build a strictly better pricing from p. The pricing will lose some revenue from edges in and will obtain more revenue from edges in .
Let . We can assume that , otherwise p cannot be optimal since we can increase the revenue by simply increasing the price of every edge to . Moreover, from the optimality of p, it is clear that we can assume also that is in . Given a pricing and a node v, we will denote by the distance of v from r in . At the beginning, is defined as p except that and for every edge e not belonging to . Notice that, for every vertex v, . We first modify prices of the edges in . We repeatedly perform the following. If there is a node v such that , we consider the path P from r to v in . Let be the edges of along the path P in the order we encounter them when we traverse P from r to v. If , then we set for every . Otherwise, let k be the minimum index such that , we first decrease by , and then we set for each . We stop when there is no edge left to be decreased. Notice that, when this happens, we have decreased each edge in at most by a and it is easy to see that the revenue of obtained from edges in decreases by at most since all the edges belonging to a path in which was decreased by at least a will still be selected by the follower.
We then consider edges in . First of all we set to , for every . Let be the set of edges entering in some vertex with . For any pricing , we use to denote the set . Observe that , since priceable edges in are priced to infinity. We now modify in order to guarantee that . We repeatedly perform the following. Consider the first node when we traverse the fixed-cost path from r to such that . Since we have decreased the prices of edges in , we have belongs to . Then, we increase the price of by . Moreover, observe that for the same reason, we have that still belongs to the new SPT computed by the follower and, since the paths that are increasing their length are paths using the edge , then no other edge exits from the SPT. We repeatedly use this argument until for every node we have . Now, it is easy to see that must be equal to .
We are now ready to bound the revenue of . We have already observed that the revenue we may lose from edges in is upper bounded by , while we do not lose revenue from edges in . On the other hand, we can now bound the increment of the revenue we obtain from all the edges . Notice that every edge is now selected in . We consider two cases:
Since is in and since , we have . Moreover, since the price of every edge increased by at least a, we have that which is strictly greater than when .
When , no edge was selected in . As a consequence, we have which is strictly greater than when , since .
Otherwise, when , we have that no edge with was selected in . Hence, since the price of every edge with has been increased by at least a, we have that , which is strictly greater than when .
In any optimal pricing for the instance of the ASSPT game, edges in must be priced according to the above lemma and thus they yield to a revenue of . Moreover, once edges in have fixed prices, the instance is very similar to the unweighted star instance of the reduction of Theorem 5. Indeed, every vertex and every vertex has distance 1 from r in the graph , and is defined as in the proof of Theorem 5. Hence, by using the same arguments given in the proof of Lemma 2, we can show that the instance of the ASSPT game has a pricing yielding a revenue of at least if and only if I admits a cover of size at most k. □