On the Complexity of the Minimum-(k,rho)-Shortcut Problem
Pith reviewed 2026-05-14 18:25 UTC · model grok-4.3
The pith
The minimum (k,ρ)-shortcut problem is NP-hard for k≥2 and ρ≥k+2 in both directed and undirected graphs.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
A simpler and more direct reduction from the Hitting Set problem establishes that min(k,ρ)-Shortcut is NP-hard for k≥2 and ρ≥k+2 in both directed and undirected graphs. Complementing this, the symmetry of the undirected case shows that ρ=k+1 is solvable in polynomial time, while the directed version with ρ=k+1 remains open.
What carries the argument
A polynomial-time reduction from Hitting Set instances to (k,ρ)-shortcut instances that preserves yes/no answers.
If this is right
- For every k≥2 and ρ≥k+2 the problem is NP-hard in undirected graphs.
- The undirected case with ρ exactly k+1 admits a polynomial-time algorithm.
- The directed case with ρ=k+1 is the single remaining open complexity question.
- The cases k=1 and k≥ρ remain polynomial-time solvable as previously known.
Where Pith is reading between the lines
- The same reduction technique may apply to other hop-constrained graph augmentation problems.
- Approximation algorithms become the natural next target for the remaining directed open case.
- The tractability threshold at ρ=k+1 in undirected graphs highlights how undirected symmetry simplifies the search for shortcuts.
Load-bearing premise
The reduction must map hitting-set instances to shortcut instances in polynomial time such that the minimum shortcut count is at most the target value exactly when a small hitting set exists.
What would settle it
A concrete undirected graph on which the optimal (2,4)-shortcut set size differs from the value predicted by the corresponding hitting-set instance would falsify the reduction.
read the original abstract
We consider the Minimum-$(k,\rho)$-$\mathrm{Shortcut}$ problem ($\min(k,\rho)\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 $\rho$ 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\rho$. While recent work by Leonhardt, Meyer, and Penschuck (ESA 2024) showed that in undirected graphs $\min(k,\rho)\text{-}\mathrm{Shortcut}$ is NP-hard for $k\geq 3$ if $\rho=\Theta(n^\epsilon)$, 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,\rho)\text{-}\mathrm{Shortcut}$ is NP-hard for $k\geq2$ and $\rho\geq k+2$ in both directed and undirected graphs. Complementing this, we use the symmetry of the undirected case to show that $\rho=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,\rho)\text{-}\mathrm{Shortcut}$, with the sole remaining open case being $\rho = k+1$ in the directed setting.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript presents a simpler and more direct reduction from the Hitting Set problem to prove that the Minimum-(k,ρ)-Shortcut problem is NP-hard for k≥2 and ρ≥k+2 in both directed and undirected graphs. It complements this with a polynomial-time algorithm for the undirected case when ρ=k+1, based on symmetry, leaving the directed ρ=k+1 case as the only open question. This nearly completes the complexity characterization of the problem.
Significance. If the reduction holds, this result significantly advances the understanding of the complexity of min(k,ρ)-Shortcut, a problem relevant to accelerating parallel shortest path algorithms. It narrows the gap left by prior work (Leonhardt et al., ESA 2024) by showing hardness for smaller ρ values (ρ ≥ k+2) and provides a clean poly-time result for the boundary case in undirected graphs. The direct reduction from Hitting Set and the use of symmetry are strengths that make the contribution clear and potentially impactful for the field.
minor comments (2)
- [Abstract] Abstract: The abstract states that the directed version for ρ=k+1 'remains a candidate for NP-hardness'; this phrasing is slightly speculative and could be replaced with 'remains open' to maintain neutrality.
- [Reduction section] The reduction construction (presumably §3) should explicitly state the polynomial-time computability of the mapping and verify that no extra shortcuts violate the distance-k constraint in yes/no instances.
Simulated Author's Rebuttal
We thank the referee for their positive assessment of the manuscript and for recommending minor revision. We appreciate the recognition that our direct reduction from Hitting Set and the symmetry-based polynomial-time algorithm for the undirected boundary case strengthen the complexity characterization of the Minimum-(k,ρ)-Shortcut problem.
Circularity Check
No significant circularity detected
full rationale
The paper's central result is a direct polynomial-time reduction from the independent Hitting Set problem to establish NP-hardness for k≥2 and ρ≥k+2. This is a standard one-way Karp reduction that preserves yes/no answers without self-referential equations, fitted parameters, or ansatzes. The cited prior work (Leonhardt et al., ESA 2024) supplies only contextual background on a different hardness regime and is not invoked to justify the new reduction or the undirected ρ=k+1 polynomial-time claim, which rests on symmetry arguments. No load-bearing step reduces to a self-citation chain or renames a known result as a derivation; the proof chain is externally grounded in a classic NP-complete problem.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Hitting Set is NP-hard
Reference graph
Works this paper leans on
- [1]
-
[2]
Alexander Leonhardt and Ulrich Meyer and Manuel Penschuck , title =. 2024 , doi =
work page 2024
-
[3]
Bruno Courcelle , title =. Inf. Comput. , volume =. 1990 , url =. doi:10.1016/0890-5401(90)90043-H , timestamp =
-
[4]
Edith Cohen and Eran Halperin and Haim Kaplan and Uri Zwick , title =. 2003 , doi =
work page 2003
-
[5]
Berndt and Sun Kim and Alexandru Zaharescu , title =
Bruce C. Berndt and Sun Kim and Alexandru Zaharescu , title =. Am. Math. Mon. , volume =. 2018 , doi =
work page 2018
-
[6]
Richard M. Karp , title =. Complexity of Computer Computations , series =. 1972 , doi =
work page 1972
-
[7]
Subhash Khot and Oded Regev , title =. J. Comput. Syst. Sci. , volume =. 2008 , doi =
work page 2008
-
[8]
Blelloch and Yan Gu and Yihan Sun and Kanat Tangwongsan , title =
Guy E. Blelloch and Yan Gu and Yihan Sun and Kanat Tangwongsan , title =. 2016 , doi =
work page 2016
-
[9]
Ulrich Meyer and Peter Sanders , title =. J. Algorithms , volume =. 2003 , doi =
work page 2003
-
[10]
Xiaojun Dong and Yan Gu and Yihan Sun and Yunming Zhang , title =. 2021 , doi =
work page 2021
-
[11]
Maxim A. Babenko and Andrew V. Goldberg and Haim Kaplan and Ruslan Savchenko and Mathias Weller , title =. 2015 , doi =
work page 2015
-
[12]
Edsger W. Dijkstra , title =. Edsger Wybe Dijkstra , series =. 2022 , doi =
work page 2022
-
[13]
Robert Geisberger and Peter Sanders and Dominik Schultes and Daniel Delling , title =. 2008 , doi =
work page 2008
- [14]
- [15]
-
[16]
Parameterized Complexity Theory , series =
J. Parameterized Complexity Theory , series =. 2006 , doi =
work page 2006
-
[17]
Uriel Feige , title =. J. 1998 , doi =
work page 1998
-
[18]
ON A ROUTING PROBLEM , urldate =
Richard Bellman , journal =. ON A ROUTING PROBLEM , urldate =
-
[19]
Rand Corporation Paper, Santa Monica, 1956 , year=
Network Flow Theory , author=. Rand Corporation Paper, Santa Monica, 1956 , year=
work page 1956
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.