Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.07771 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916122501054464 |
|---|---|
| author | Leonhardt, Alexander Meyer, Ulrich Penschuck, Manuel |
| author_facet | Leonhardt, Alexander Meyer, Ulrich Penschuck, Manuel |
| contents | 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 \ge 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_07771 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Insights into $(k,ρ)$-shortcutting algorithms Leonhardt, Alexander Meyer, Ulrich Penschuck, Manuel Data Structures and 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 \ge 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. |
| title | Insights into $(k,ρ)$-shortcutting algorithms |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.07771 |