# On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem

Preprint · Tatiana Rocha Avila, Julian Christoph Brinkmann, Alexander Leonhardt, Conrad Schecker

- Archive id: arxiv:2605.13474
- Published: 2026-05-13
- arXiv: https://arxiv.org/abs/2605.13474
- Source URL: https://arxiv.org/abs/2605.13474
- PDF: https://arxiv.org/pdf/2605.13474
- Provenance: arxiv

## Abstract

We consider the Minimum-$(k,ρ)$-$\\mathrm{Shortcut}$ problem ($\\min(k,ρ)\\text{-}\\mathrm{Shortcut}$), where the goal is to find the smallest set of shortcut edges such that every vertex in a given graph can reach its $ρ$ closest vertices using paths of at most $k$ edges. This is a fundamental graph optimization problem used to accelerate parallel shortest path algorithms. It is well-known that the problem is trivially solvable for the cases $k=1$ and $k\\geqρ$. While recent work by Leonhardt, Meyer, and Penschuck (ESA 2024) showed that in undirected graphs $\\min(k,ρ)\\text{-}\\mathrm{Shortcut}$ is NP-hard for $k\\geq 3$ if $ρ=Θ(n^ε)$, the boundary where the problem transitions from polynomial-time solvable to NP-hard remained open. In this paper, we narrow this gap significantly. We present a simpler and more direct reduction from the Hitting Set problem which establishes that $\\min(k,ρ)\\text{-}\\mathrm{Shortcut}$ is NP-hard for $k\\geq2$ and $ρ\\geq k+2$ in both directed and undirected graphs. Complementing this, we use the symmetry of the undirected case to show that $ρ=k+1$ is solvable in polynomial time, a regime where the directed version remains a candidate for NP-hardness. Therefore, we obtain an almost complete characterization of the complexity of $\\min(k,ρ)\\text{-}\\mathrm{Shortcut}$, with the sole remaining open case being $ρ= k+1$ in the directed setting.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.