  In routing games, the network performance at equilibrium can be significantly
improved if we remove some edges from the network. This counterintuitive fact,
widely known as Braess's paradox, gives rise to the (selfish) network design
problem, where we seek to recognize routing games suffering from the paradox,
and to improve the equilibrium performance by edge removal. In this work, we
investigate the computational complexity and the approximability of the network
design problem for non-atomic bottleneck routing games, where the individual
cost of each player is the bottleneck cost of her path, and the social cost is
the bottleneck cost of the network. We first show that bottleneck routing games
do not suffer from Braess's paradox either if the network is series-parallel,
or if we consider only subpath-optimal Nash flows. On the negative side, we
prove that even for games with strictly increasing linear latencies, it is
NP-hard not only to recognize instances suffering from the paradox, but also to
distinguish between instances for which the Price of Anarchy (PoA) can decrease
to 1 and instances for which the PoA is as large as \Omega(n^{0.121}) and
cannot improve by edge removal. Thus, the network design problem for such games
is NP-hard to approximate within a factor of O(n^{0.121-\eps}), for any
constant \eps > 0. On the positive side, we show how to compute an almost
optimal subnetwork w.r.t. the bottleneck cost of its worst Nash flow, when the
worst Nash flow in the best subnetwork routes a non-negligible amount of flow
on all used edges. The running time is determined by the total number of paths,
and is quasipolynomial when the number of paths is quasipolynomial.
