# Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game +
## 4 Dealing with Basic Network Topologies
### Unweighted Stars  
In this section, we focus on instances where edges in \(C\) have cost \(1\) and form a star emanating from the source node \(r\). We show that the problem of finding a pricing maximizing the revenue is equivalent to another problem known in literature as the _Rooted Maximum Leaf Outbranching (RMLO) problem_, which asks for finding a spanning arborescence rooted at some prescribed vertex of a digraph with the maximum number of leaves. This problem is known to be NP-hard even when restricted to DAGs [22] and even MaxSNP-hard on undirected graphs [24]. Moreover, it admits a 92-approximation algorithm [21]. Hence, the equivalence result immediately implies the existence of a constant-factor approximation algorithm for our problem, with the same approximation ratio. Moreover, we improve the inapproximability result for the RMLO problem by showing that it is APX-hard even for DAGs. First, we observe that we can restrict ourselves to consider instances of pricing where all nodes can be reached by a path of priceable edges, since any other node would be reached through a single fixed-cost edge in any SPT computed by the follower, and thus it cannot influence the revenue. We can prove the following:  
**Lemma 1**: _Let \(G=(V,C\cup P)\) be an instance of the ASSPT game where edges in \(C\) have unitary cost and form a star rooted at \(r\). Then, \(G\) admits a pricing with revenue greater than or equal to \(k\in\mathbb{N}\) if and only if \(G^{\prime}=(V,P)\) has a spanning arborescence rooted at \(r\) with at least \(k\) leaves._  
Proof. : Let \(T\) be a spanning arborescence of \(G^{\prime}\) rooted at \(r\) with at least \(k\) leaves. Then, we can define the following pricing for \(G\): \(p(e)=1\), if \(e\) enters into a leaf of \(T\), \(0\) otherwise. It is easy to see that such a pricing yields a revenue of \(k\), since \(T\) is a SPT of \(G\). On the other hand, let us consider a pricing \(p\) with revenue \(R\geq k\). Let \(T\) be the SPT computed by the follower after the leader prices her edges according to \(p\), and let \((r,v)\)be an edge of \(T\). Then, all the edges of the subtree of \(T\) rooted at \(v\), say \(T(v)\), must be priceable edges. Moreover, if \((r,v)\) is a fixed-cost edge, then all the edges in \(T(v)\) must have price 0. Now, let \(T^{\prime}\) be the subtree of \(T\) obtained by removing every fixed-cost edge \((r,v)\) and the corresponding subtree \(T(v)\). From the arguments given above, we have that \(R=\sum_{e\in E(T^{\prime})}p(e)\). Now, we show that the number of leaves of \(T^{\prime}\), say \(\ell\), is at least \(R\). Indeed, we have that  
\[R=\sum_{e\in E(T^{\prime})}p(e)\leq\sum_{v\,|\,v\text{ is a leaf in }T^{\prime}}d_{T^{ \prime}}(r,v)\leq\ell,\]  
where the last inequality holds since \(T^{\prime}\) is a subtree of a SPT of \(G\), which implies that, for each node \(v\), \(d_{T^{\prime}}(r,v)\leq 1\). Now, notice that \(T^{\prime}\) is an arborescence rooted at \(r\) of \(G^{\prime}\) as well, but it may not span \(V\). However, we can add priceable edges to \(T^{\prime}\) in order to make it spanning. This does not decrease the number of leaves. Theorem 4.1: _The ASSPT game where the edges of \(C\) have unitary cost and form a star rooted at \(r\) is \(\mathsf{APX}\)-hard._  
Proof: The reduction is from _Set Cover problem (SCP)_. An instance \(I=\langle O,\mathcal{S}\rangle\) of SCP consists of a set \(O=\{o_{1},\ldots,o_{n}\}\) of objects and a set \(\mathcal{S}=\{S_{1},\ldots,S_{m}\}\) of \(m\) subset of \(O\). The objective is to find a minimum-size collection of subsets in \(\mathcal{S}\) whose union is \(O\). In [25], it is shown that SCP is \(\mathsf{NP}\)-hard. Given an instance \(I=\langle O,\mathcal{S}\rangle\) of SCP, we build the following instance of the ASSPT game. We have the root vertex \(r\), a node \(u_{j}\) for each \(S_{j}\), and a node \(v_{i}\) for each \(o_{i}\). There is a fixed-cost edge (of cost 1) from \(r\) to each other node.