{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreie5v6p34o4kioy4bronjb7ybvmgsdsbloncsu45s6wa3a5jv6laji",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mls3sedjwze2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.13474v1",
  "publishedAt": "2026-05-14T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Tatiana Rocha Avila",
    "Julian Christoph Brinkmann",
    "Alexander Leonhardt",
    "Conrad Schecker"
  ],
  "textContent": "**Authors:** Tatiana Rocha Avila, Julian Christoph Brinkmann, Alexander Leonhardt, Conrad Schecker\n\nWe 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.",
  "title": "On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem"
}