Insights into (k,ρ)-shortcutting algorithms

A graph is called a (k,ρ)-graph iff every node can reach ρ 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,ρ)-graph by adding shortcuts. Formally, the (k,ρ)-Minimum-Shortcut problem asks to find an appropriate shortcut set of minimal cardinality. We show that the (k,ρ)-Minimum-Shortcut problem is NP-complete in the practical regime of k ≥ 3 and ρ = Θ(n^ε) for ε > 0. With a related construction, we bound the approximation factor of known (k,ρ)-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,ρ)-Minimum-Shortcut problem optimally. Finally, we compare the practical performance and quality of all algorithms in an empirical campaign.