Insights into $(k,\rho)$-shortcutting algorithms
<|reference_start|>Insights into $(k,\rho)$-shortcutting algorithms: 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.<|reference_end|>
@article{leonhardt2024insights,
    title={Insights into $(k,\rho)$-shortcutting algorithms},
    author={Alexander Leonhardt, Ulrich Meyer and Manuel Penschuck},
    journal={arXiv preprint arXiv:2402.07771},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.07771},
    primaryClass={cs.DS}
}