💻 computer science

$\tilde{O}$ ptimal Algorithm for 2-Approximate All Pair Shortest Paths -- almost

This paper presents a randomized algorithm combining combinatorial techniques with fast matrix multiplication to compute a 2-approximation of all-pairs shortest paths in undirected, unweighted graphs in $\tilde{O}(n^2)$ time, guaranteeing accuracy for all pairs at distance at least a constant $c \ge 0$ .

Original authors: Manoj Gupta, Mrigankashekhar Shandilya

Published 2026-07-22

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Manoj Gupta, Mrigankashekhar Shandilya

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a delivery driver in a massive, sprawling city where every street is exactly the same length. Your job is to figure out the quickest route between every possible pair of addresses in the city. If the city has a million houses, that's a trillion different routes to calculate. In the world of computer science, this is called the "All-Pairs Shortest Path" problem. It's the digital equivalent of trying to map every single shortcut in a labyrinth.

For decades, computers have been great at finding these routes, but there's a catch: the more accurate the map, the longer it takes to draw. If you want the perfect route, the computer might have to work so hard it takes forever, especially in huge cities. But what if you're okay with a route that is "good enough"—say, no more than twice as long as the absolute best path? This is called a "2-approximation." It's like telling a driver, "Don't worry about finding the single perfect shortcut; just give me a route that won't make you late by more than a factor of two." The big question for scientists has been: Can we draw this "good enough" map for a whole city of a million houses almost as fast as it takes to just write down the list of all the houses?

This paper, written by Manoj Gupta and Mrigankashekhar Shandilya, tackles that exact challenge. They have designed a new, clever method to create these "good enough" maps for almost every pair of locations in a city, and they do it with a speed that is nearly as fast as theoretically possible.

The Problem: The Trillion-Route Nightmare

Let's say you have a graph, which is just a fancy word for a network of dots (vertices) connected by lines (edges). Think of the dots as people at a party and the lines as friendships. If you want to know the shortest chain of introductions between any two people, that's a shortest path.

If the party is small, you can just ask everyone. But if the party has $n$ people, there are $n^2$ (n times n) pairs of people. If $n$ is a million, $n^2$ is a trillion. The paper notes that simply writing down the answer for every pair takes time proportional to this trillion. So, the "speed limit" for this problem is $n^2$ . You can't go faster than that because you have to write down the answer.

The goal of this research is to hit that speed limit. They want an algorithm that runs in roughly $n^2$ time (specifically, $\tilde{O}(n^2)$ , which hides some tiny, annoying math factors) and guarantees that the route it finds is at most twice the length of the true shortest path.

The Old Ways: Guessing and Checking

Before this paper, scientists had tried to solve this. Some methods were like trying to find a needle in a haystack by checking every single piece of hay. Others were smarter but still had a blind spot.

One famous approach by Dor, Halperin, and Zwick could find these "good enough" routes very quickly, but only for people who were already far apart (at least $O(\log n)$ steps away). If two people were sitting right next to each other, the method might fail or be slow. A more recent improvement by Gupta (in 2025) pushed this boundary, handling people who were at least $O(\log \log n)$ steps apart. But there was still a tiny gap: what about people who are just a few steps away? The old methods couldn't guarantee the "twice as long" rule for everyone while staying super fast.

The New Idea: The "Ball" and the "Cluster"

The authors' solution is a mix of two different strategies: a careful, step-by-step combinatorial approach and a powerful mathematical trick called Fast Matrix Multiplication (FMM).

To understand their trick, imagine the party again. They pick a few random people to be "Pivots."

The Ball: Around every person, they draw an invisible "ball" containing everyone who is closer to them than to their nearest Pivot.
The Cluster: Conversely, a "Cluster" is the group of people whose balls contain a specific person.

The magic insight is that for most people, these "Balls" are small and manageable. If you are inside someone's Ball, you are close to them, and you can find the exact distance quickly.

The path between two people, let's call them Alice and Bob, can be broken into three parts:

The Prefix: Alice walking to the edge of her Ball.
The Middle: The walk from the edge of Alice's Ball to the edge of Bob's Ball.
The Suffix: Bob walking from the edge of his Ball to his destination.

The authors realized that the Prefix and Suffix are easy because they happen inside these small, low-degree Balls. The tricky part is the Middle. If the Middle is short, they can just guess and check. If the Middle is long, they need a different tactic.

The Two-Pronged Attack: Sparse vs. Dense

The paper splits the problem into two scenarios based on how many people are "close" to a specific point on the path.

Scenario A: The Sparse Case (Few Neighbors)
Imagine the middle part of the path is surrounded by very few people. In this case, the algorithm simply checks every possible pair of "close" people. Because there are so few of them, this check is fast. It's like checking every possible shortcut in a quiet neighborhood; you can do it quickly because there aren't many streets.

Scenario B: The Dense Case (Many Neighbors)
Now, imagine the middle part is in a crowded city center with thousands of people nearby. Checking every single pair here would take forever. This is where the authors bring in the "Fast Matrix Multiplication" (FMM).

Think of FMM as a super-powerful calculator that can multiply huge grids of numbers almost instantly. The authors create a small, random sample of people (a "Lucky Set") from the crowd. They use the FMM calculator to check if anyone in this Lucky Set can serve as a stepping stone between Alice and Bob.

Here is the clever part: Because the middle section of the path is guaranteed to be short (a constant number of steps), and because the "Lucky Set" is chosen randomly, there is a very high probability that at least one person in the Lucky Set is standing right on that short middle path. The FMM calculator then instantly computes the distances through this lucky person, giving a "good enough" estimate for the whole trip.

The Result: A Near-Perfect Map

By combining these two strategies, the authors prove that they can find a route that is at most twice the true distance for all pairs of people who are at least a constant number of steps apart (specifically, a distance of at least $c$ , where $c$ is a constant like 906).

The paper shows that this can be done in $\tilde{O}(n^2)$ time. This is a massive improvement because it means the algorithm is as fast as the theoretical limit allows (since you have to write down $n^2$ answers).

What This Means

The paper doesn't just suggest this might work; they provide a rigorous mathematical proof that their randomized algorithm works with "high probability" (meaning it works almost every time you run it).

They explicitly rule out the idea that you need to check every pair of people to get this speed. Instead, they show that by splitting the problem into "sparse" (check everything) and "dense" (use the lucky sample and math magic), you can bypass the slow parts.

While they don't claim to have solved the problem for every single pair (specifically, pairs that are extremely close, like 1 or 2 steps apart, might need a different constant), they have nearly resolved the problem for the vast majority of cases. They have bridged the gap between the old methods that worked for distant pairs and the need for a method that works for everyone, all while keeping the speed record intact.

In short, they found a way to draw a "good enough" map of a trillion-route city in the time it takes to list the city's population, using a mix of careful walking and a super-calculator to skip the boring parts.

Technical Summary: Optimal Algorithm for 2-Approximate All Pair Shortest Paths

Problem Statement
The paper addresses the problem of computing a 2-approximation of All-Pairs Shortest Paths (2-APSP) in an undirected, unweighted graph $G$ with $n$ vertices. While the output size is $\Theta(n^2)$ , implying a lower bound of $\Omega(n^2)$ , the central goal is to achieve a running time of $\tilde{O}(n^2)$ (nearly quadratic). Previous work by Dor, Halperin, and Zwick (DHZ00) achieved this time complexity but only for pairs at a distance of at least $O(\log n)$ . More recently, Gupta (Gup25) improved this to pairs at a distance of $O(\log \log n)$ . The open problem remains to design a 2-APSP algorithm running in $\tilde{O}(n^2)$ that works for all pairs at a distance of at least a constant $c \ge 0$ .

Methodology
The proposed algorithm is a randomized approach that combines combinatorial techniques with Fast Matrix Multiplication (FMM). The methodology relies on a structural decomposition of the shortest path between any two vertices $s$ and $t$ , facilitated by a modified nested vertex sampling scheme.

Modified Nested Sampling and Clustering:
The algorithm employs a sampling strategy to define sets of vertices $A_i$ and associated "balls" ( $ball_i(s)$ ) and "clusters" ( $cluster_i(s)$ ). Unlike previous works that only bounded ball sizes, this paper adapts a result by Thorup and Zwick to ensure that for a specific level $\alpha$ , both the ball size $|ball_\alpha(s)|$ and the cluster size $|cluster_\alpha(s)|$ are bounded by $\tilde{O}(2^{2\alpha})$ . This bounded cluster size is crucial for the algorithm's efficiency.
Path Decomposition:
For a pair $(s, t)$ , the shortest path is analyzed relative to the boundaries of the balls $ball_\alpha(s)$ and $ball_\alpha(t)$ . The path is decomposed into three segments:
- Prefix ( $s \to p_s$ ): A path from $s$ to the boundary of its ball. Vertices strictly inside this segment have low degree.
- Suffix ( $p_t \to t$ ): A path from the boundary of $t$ 's ball to $t$ . Similarly, these vertices have low degree.
- Middle Segment ( $p_s \to p_t$ ): The segment connecting the boundaries of the two balls.
The core technical insight is proving that the middle segment $p_s p_t$ is short (bounded by a constant $c$ ). This is established via a subroutine ENSUREBALLPROXIMITY, which ensures that either a 2-approximation is already found, or the balls of $s$ and $t$ are sufficiently close such that $|p_s p_t| \le c$ .
Sparse vs. Dense Case Handling:
To compute the distance efficiently, the algorithm iterates over candidate vertices $x$ (potential boundary points) and checks pairs in their clusters. The approach splits based on the size of the set $ESTIMATEDCLOSE(x)$, which contains vertices within a constant distance of $x$ :
- Sparse Case ( $|ESTIMATEDCLOSE(x)| \le n^{0.875}$ ): The algorithm explicitly enumerates pairs $(x, y)$ where $y \in ESTIMATEDCLOSE(x)$ . Due to the bounded cluster sizes and the sparse condition, this step runs in $\tilde{O}(n^2)$ .
- Dense Case ( $|ESTIMATEDCLOSE(x)| > n^{0.875}$ ): When the set of close vertices is large, the algorithm uses a random sample $L$ of vertices. It constructs a subgraph $G(\gamma)$ containing only low-degree edges (degree $\le \tilde{O}(\gamma)$ ). It is proven that the shortest path between $s$ and $t$ (and the path to a sampled vertex $z \in L$ ) lies entirely within $G(\gamma)$ .
- Fast Matrix Multiplication (FMM): For the dense case, the algorithm computes distance estimates using the min-plus product (distance product) of two matrices derived from the estimates in $G(\gamma)$ . Specifically, it multiplies an $n \times \tilde{O}(n^{0.125})$ matrix with an $\tilde{O}(n^{0.125}) \times n$ matrix. Using known results on rectangular matrix multiplication where the inner dimension is small ( $r \le 0.17227$ ), this product can be computed in $\tilde{O}(n^2)$ time.

Key Contributions

Resolution of the Constant Distance Bound: The paper presents a randomized algorithm that computes a 2-approximation for all pairs at distance at least a constant $c$ (specifically $c \le 906$ ) in $\tilde{O}(n^2)$ time. This nearly resolves the open problem of achieving $\tilde{O}(n^2)$ for 2-APSP beyond logarithmic distance thresholds.
Integration of FMM with Combinatorial Techniques: Unlike previous purely combinatorial approaches (e.g., DHZ00, Gup25), this work crucially integrates Fast Matrix Multiplication to handle the "dense" case of the algorithm, allowing it to bypass the $\tilde{O}(n^{2+\epsilon})$ barrier inherent in purely combinatorial methods for this specific approximation.
Bounded Cluster Sizes: The adaptation of Thorup and Zwick's sampling to bound cluster sizes (not just ball sizes) is a structural contribution that enables the efficient enumeration in the sparse case.

Results
The main theorem states that there exists a randomized algorithm that, with high probability, runs in $\tilde{O}(n^2)$ time and guarantees a 2-approximation for all pairs of vertices at a distance of at least a constant $c \ge 0$ . The algorithm achieves a constant additive approximation ($|st| + O(1)$) for pairs at distance $\ge c$ , which implies a 2-multiplicative approximation for sufficiently large distances.

Significance
The paper claims to "nearly resolve" the problem of designing a 2-APSP algorithm with nearly quadratic running time for all pairs at a constant distance. By combining combinatorial structural insights (low-degree paths, bounded clusters) with the power of Fast Matrix Multiplication, the authors bridge the gap between the $\tilde{O}(n^2)$ time complexity and the requirement to handle pairs at constant distances, a feat previously unattained by purely combinatorial algorithms. The work demonstrates that the combination of these techniques is sufficient to achieve the optimal time complexity for 2-approximation, provided the distance threshold is a constant rather than a function of $n$ .