New sampling trick tightens a 1996 shortest-path guarantee for nearby pairs

An IIT Gandhinagar algorithm extends a 30-year-old approximation guarantee to closer vertex pairs without slowing the computation.

Manoj Gupta, an Associate Professor at IIT Gandhinagar, has developed a new algorithm for approximate all-pairs shortest paths (APSP), the problem of finding the shortest distance between every pair of points in a network. He presented it at FOCS 2025, the 66th Annual Symposium on Foundations of Computer Science, in a paper titled "Improved 2-Approximate Shortest Paths for close vertex pairs." This is theoretical computer science, not a shipped product.

The starting point is a 1996 method by Dor, Halperin and Zwick. It returns distance estimates within twice the true distance, in nearly optimal time, but only for vertex pairs that are sufficiently far apart. It works by sampling a small set of vertices that act as shortcuts. For close pairs, those sampled vertices can sit far from the direct path, so a true 2-edge path might be estimated as a 5-edge route.

Gupta's approach uses multi-scale sampling, organizing network information at several levels rather than one sampling layer. That lowers the minimum distance at which the 2-approximation guarantee holds, while keeping the same overall runtime as the earlier method. The contrast matters because some conventional exact APSP approaches on dense graphs take cubic time, so doubling the vertices raises work roughly eightfold.

The abundance case is indirect. Shortest-path calculations sit underneath routing, search and network analysis, so reliable approximations that stay fast on huge graphs could, over time, lower the compute needed for mobility and communication systems. Nothing here is deployed, and no cost savings have been measured.

Caveats: the result is a 2-approximation, so an estimate may be up to twice the true distance, not an exact answer. The source is a university press release, so its significance claims haven't been independently assessed, and the text we saw was truncated before its practical-impact discussion. Watch for peer commentary and whether implementations show real gains.

Source: ScienceDaily