  A graph is called a $(k,\rho)$-graph iff every node can reach $\rho$ of its
nearest neighbors in at most k hops. This property proved useful in the
analysis and design of parallel shortest-path algorithms. Any graph can be
transformed into a $(k,\rho)$-graph by adding shortcuts. Formally, the
$(k,\rho)$-Minimum-Shortcut problem asks to find an appropriate shortcut set of
minimal cardinality.
  We show that the $(k,\rho)$-Minimum-Shortcut problem is NP-complete in the
practical regime of $k \ge 3$ and $\rho = \Theta(n^\epsilon)$ for $\epsilon >
0$. With a related construction, we bound the approximation factor of known
$(k,\rho)$-Minimum-Shortcut problem heuristics from below and propose
algorithmic countermeasures improving the approximation quality. Further, we
describe an integer linear problem (ILP) solving the
$(k,\rho)$-Minimum-Shortcut problem optimally. Finally, we compare the
practical performance and quality of all algorithms in an empirical campaign.
