Abstract | Braess’s paradox states that removing a part of a network may im-
prove the players’ latency at equilibrium. In this work, we study the approxima-
bility of the best subnetwork problem for the class of random
G
n;p
instances
proven prone to Braess’s paradox by (Roughgarden and Valiant, RSA 2010) and
(Chung and Young, WINE 2010). Our main contribution is a polynomial-time
approximation-preserving reduction of the best subnetwork problem for such in-
stances to the corresponding problem in a simplified network where all neighbors
of
s
and
t
are directly connected by
0
latency edges. Building on this, we obtain
an approximation scheme that for any constant
" >
0
and with high probabil-
ity, computes a subnetwork and an
"
-Nash flow with maximum latency at most
(1+
"
)
L
+
"
, where
L
is the equilibrium latency of the best subnetwork. Our ap-
proximation scheme runs in polynomial time if the random network has average
degree
O
(poly(ln
n
))
and the traffic rate is
O
(poly(lnln
n
))
, and in quasipoly-
nomial time for average degrees up to
o
(
n
)
and traffic rates of
O
(poly(ln
n
))
. |