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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-02
Main Authors: Leonhardt, Alexander, Meyer, Ulrich, Penschuck, Manuel
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Empirical analysis
Mathematical analysis
Shortest-path problems
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422