2026-08-19T10:43:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21155 2024-11-27T23:17:45Z ddc:004 open_access

Insights into (k, ρ)-Shortcutting Algorithms Leonhardt, Alexander Meyer, Ulrich Penschuck, Manuel Complexity Approximation Optimal algorithms Parallel shortest path A graph is called a (k, ρ)-graph iff every node can reach ρ of its nearest neighbors in at most k hops. This property has proven useful in the analysis and design of parallel shortest-path algorithms [Blelloch et al., 2016; Dong et al., 2021]. Any graph can be transformed into a (k, ρ)-graph by adding shortcuts. Formally, the (k,ρ)-Minimum-Shortcut-Problem (kρ-MSP) asks to find an appropriate shortcut set of minimal cardinality. We show that kρ-MSP 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ρ-MSP heuristics [Blelloch et al., 2016] from below and propose algorithmic countermeasures improving the approximation quality. Further, we describe an integer linear problem (ILP) that optimally solves kρ-MSP. Finally, we compare the practical performance and quality of all algorithms empirically. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Leonhardt and Ulrich Meyer and Manuel Penschuck 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.84 urn:nbn:de:0030-drops-211554 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.84 eng https://creativecommons.org/licenses/by/4.0/legalcode