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

あなたは、すべての通りが全く同じ長さである、巨大で広大な都市の配達ドライバーであると想像してください。あなたの仕事は、その都市にあるあらゆる可能な住所間の最短ルートを見つけ出すことです。もし都市に100万軒の家があれば、1兆通りのルートを計算しなければなりません。コンピュータサイエンスの世界では、これは「全対最短経路（All-Pairs Shortest Path）」問題と呼ばれます。これは、迷宮の中のあらゆるショートカットをマッピングしようとするデジタル的な試みです。

数十年の間、コンピュータはこれらのルートを見つけることに長けてきましたが、一つ問題があります。それは、地図が正確になればなるほど、それを描くのに時間がかかるということです。もし「完璧な」ルートを求めれば、コンピュータは膨大な作業を強いられ、特に巨大な都市では永遠に終わらないかもしれません。しかし、もし「十分に良い」ルートで満足できるとしたのであればどうでしょう。例えば、絶対的な最短経路の2倍以内の長さで構わないとしたら？ これはドライバーに対して、「たった一つの完璧なショートカットを見つける必要はありません。ただ、到着が（最短経路の）2倍の速さ以上遅れないようにしてください」と伝えるようなものです。これを「2近似（2-approximation）」と呼びます。大きな疑問は、科学者たちがこう考えたことです。「100万軒の家がある都市全体の『十分に良い』地図を、すべての家のリストを書き出すのとほぼ同じ速さで描けるのだろうか？」

Manoj GuptaとMrigankaslekhar Shandilyaによるこの論文は、まさにその課題に取り組んでいます。彼らは、ほとんどすべての場所のペアに対して「十分に良い」地図を作成する、新しい巧妙な手法を設計しました。しかも、それは理論的に可能な限り速いスピードで行われます。

問題：1兆ルートの悪夢

グラフを考えてみましょう。これは、点（頂点）が線（辺）によって結ばれたネットワークのことです。点をパーティーの出席者、線を友人関係だと考えてください。もし、任意の2人の間の最短の紹介の連鎖を知りたいなら、それは最短経路となります。

パーティーが小さければ、全員に聞けば済みます。しかし、もしパーティーに $n$ 人の人がいるなら、$n^2$ （$n$ 回 $n$）のペアが存在します。もし $n$ が100万なら、$n^2$ は1兆になります。論文では、すべてのペアに対する答えを単に書き出すだけで、$n^2$ に比例する時間がかかることが指摘されています。したがって、この問題の「速度制限」は $n^2$ です。答えを書き出す必要があるため、これより速くなることはありません。

この研究の目標は、その速度制限に到達することです。彼らは、およそ $n^2$ の時間（具体的には、些細で厄介な数学的要因を隠蔽した $\tilde{O}(n^2)$）で動作し、かつ見つけたルートが真の最短経路の最大2倍であることを保証するアルゴリズムを求めています。

古い手法：推測と検証

この論文の前に、科学者たちはこれを解決しようと試みてきました。ある手法は、干し草の山の中から針を探すために、すべての干し草をチェックするようなものでした。他の手法はより賢いものでしたが、依然として盲点がありました。

Dor、Halperin、およびZwickによる有名なアプローチは、非常に高速に「十分に良い」ルートを見つけることができますが、それはすでに離れている人々（少なくとも $O(\log n)$ ステップ離れている場合）に対してのみ有効でした。もし2人がすぐ隣に座っていたら、その手法は失敗するか、あるいは遅くなってしまいます。Guptaによる最近の改善（2025年）は、この境界を押し広げ、$O(\log \log n)$ ステップ離れている人々を扱えるようにしました。しかし、まだ小さな隙間がありました。数ステップしか離れていない人々についてはどうなるのでしょうか？ 古い手法では、全員に対して「2倍以内」というルールを保証しながら、超高速を維持することができなかったのです。

新しいアイデア：「ボール」と「クラスター」

著者たちの解決策は、2つの異なる戦略の組み合わせです。一つは、注意深く段階的な組合せ論的アプローチであり、もう一つは「高速行列乗算（Fast Matrix Multiplication: FMM）」と呼ばれる強力な数学的トリックです。

このトリックを理解するために、再びパーティーを想像してください。彼らは、いくつかのランダムな人々を「ピボット（軸となる点）」として選びます。

1. ボール（球体）： すべての人の周囲に、その人が最も近いピボットよりも近い人々を含む目に見えない「ボール」を描きます。
2. クラスター（集団）： 逆に、「クラスター」とは、特定の人物をそのボールの中に含んでいる人々のグループのことです。

魔法のような洞察は、ほとんどの人にとって、これらの「ボール」は小さく扱いやすいということです。もしあなたが誰かのボールの中にいるなら、あなたは彼らに近く、距離を素早く見つけることができます。

ある人と別の人の間の経路（例えばアリスとボブ）は、以下の3つの部分に分解できます：

1. プレフィックス（接頭辞）： アリスが自分のボールの端まで歩く部分。
2. ミドル（中間部）： アリスのボールの端からボブのボールの端までの歩行。
3. サフィックス（接尾辞）： ボブが目的地まで歩く部分。

著者たちは、プレフィックスとサフィックスは、これら小さく次数が低いボールの中で起こるため、容易であることを見抜きました。難しいのは、このミドルの部分です。もしミドルが短い場合は、単に推測して検証することができます。もしミドルが長い場合は、別の戦術が必要になります。

二段構えの攻撃：疎（Sparse）か、密（Dense）か

論文は、経路上の特定の点にどれだけの人が「近い」かに基づいて、問題を2つのシナリオに分割しています。

シナリオA：疎なケース（隣人が少ない場合）
経路の中間部分が、非常に少ない人々によって囲まれている状況を想像してください。この場合、アルゴリズムは「近い」人々のあらゆる可能なペアを単純にチェックします。彼らが少ないため、このチェックは高速です。それは、静かな住宅街のあらゆるショートカットを素早くチェックするようなものです。道が少ないので、すぐに終わります。

シナリオB：密なケース（隣人が多い場合）
今度は、中間部分が、周囲に何千人もの人々がいる混雑した都心部にいる状況を想像してください。ここでのすべてのペアをチェックすることは、膨大な時間がかかります。ここで著者たちは、「高速行列乗算（FMM）」という強力な武器を持ち出します。

FMMを、巨大な数字のグリッドをほぼ瞬時に掛け合わせることができる、超強力な計算機だと考えてください。著者たちは、群衆の中からランダムに選ばれた少数の人々（「ラッキー・セット」）を作成します。そして、F المثالのように、FMM計算機を使用して、アリスとボブの間をつなぐ踏み台として機能できる人が、このラッキー・セットの中に誰か存在するかどうかをチェックします。

ここが巧妙な点です。経路のミドルセクションは、ステップ数が一定（定数）であると保証されており、かつ「ラッキー・セット」がランダムに選ばれているため、そのラッキー・セットの中に、ちょうどその短いミドルパスの上に立っている人が存在する確率が非常に高いのです。FMM計算機は、このラッキーな人物を経由した距離を即座に計算し、旅全体に対する「十分に良い」推定値を与えます。

結果：ほぼ完璧な地図

これら2つの戦略を組み合わせることで、著者たちは、すべてのペア（具体的には、少なくとも定数 $c$ ステップ、例えば $c=906$ などの距離離れているペア）に対して、真の距離の最大2倍のルートを見つけられることを証明しました。

論文は、これが $\tilde{O}(n^2)$ の時間で行えることを示しています。これは、回答を $n^2$ 個書き出す必要があるという理論的限界と同じスピードであるため、極めて大きな進歩です。

これが意味すること

この論文は、これが単に「可能かもしれない」と示唆しているだけでなく、彼らのランダム化アルゴリズムが「高い確率で（実行するたびにほぼ確実に）」機能するという厳密な数学的証明を提供しています。

彼らは、このスピードを実現するために、すべてのペアをチェックする必要があるという考えを明確に否定しています。代わりに、問題を「疎（すべてをチェックする）」と「密（ラッキー・サンプルと数学のマジックを使う）」に分割することで、遅い部分を回避できることを示しました。

彼らは、すべてのペアに対してこの問題を解決した（具体的には、1歩や2歩といった極めて近いペアについては、異なる定数が必要になる可能性があります）と主張しているわけではありませんが、大多数のケースにおいて問題をほぼ解決しました。彼らは、遠く離れたペアに対して機能していた古い手法と、すべての人に対して機能する必要がある手法との間の溝を埋め、同時にスピード記録も維持したのです。

要約すると、彼らは、丁寧な歩行とスーパー計算機による退屈な部分のスキップを組み合わせることで、1兆ルートある都市の「十分に良い」地図を、その都市の人口をリストアップするのと同等の時間で描く方法を見出したのです。