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.