  Finding important nodes in a graph and measuring their importance is a
fundamental problem in the analysis of social networks, transportation
networks, biological systems, etc. Among popular such metrics are graph
centrality, betweenness centrality (BC), and reach centrality (RC). These
measures are also very related to classic notions like diameter and radius.
Roditty and Vassilevska Williams~[STOC'13] showed that no algorithm can compute
a (3/2-\delta)-approximation of the diameter in sparse and unweighted graphs
faster that n^{2-o(1)} time unless the widely believed strong exponential time
hypothesis (SETH) is false. Abboud et al.~[SODA'15] and [SODA'16] further
analyzed these problems under the recent line of research on hardness in P.
They showed that in sparse and unweighted graphs (weighted for BC) none of
these problems can be solved faster than n^{2-o(1)} unless some popular
conjecture is false. Furthermore they ruled out a (2-\delta)-approximation for
RC, a (3/2-\delta)-approximation for Radius and a (5/3-\delta)-approximation
for computing all eccentricities of a graph for any \delta > 0. We extend these
results to the case of unweighted graphs with constant maximum degree. Through
new graph constructions we are able to obtain the same approximation and time
bounds as for sparse graphs even in unweighted bounded-degree graphs. We show
that no (3/2-\delta) approximation of Radius or Diameter,
(2-\delta)-approximation of RC, (5/3-\delta)-approximation of all
eccentricities or exact algorithm for BC exists in time n^{2-o(1)} for such
graphs and any \delta > 0. This strengthens the result for BC of Abboud et
al.~[SODA'16] by showing a hardness result for unweighted graphs, and follows
in the footsteps of Abboud et al.~[SODA'16] and Abboud and Dahlgaard~[FOCS'16]
in showing conditional lower bounds for restricted but realistic graph classes.
