  The network pricing problem (NPP) is a bilevel problem, where the leader
optimizes its revenue by deciding on the prices of certain arcs in a graph,
while expecting the followers (also known as the commodities) to choose a
shortest path based on those prices. In this paper, we investigate the
complexity of the NPP with respect to two parameters: the number of tolled
arcs, and the number of commodities. We devise a simple algorithm showing that
if the number of tolled arcs is fixed, then the problem can be solved in
polynomial time with respect to the number of commodities. In contrast, even if
there is only one commodity, once the number of tolled arcs is not fixed, the
problem becomes NP-hard. We characterize this asymmetry in the complexity with
a novel property named strong bilevel feasibility. Finally, we describe an
algorithm to generate valid inequalities to the NPP based on this property,
accommodated with numerical results to demonstrate its effectiveness in solving
the NPP with a high number of commodities.
