無向グラフの最小カット問題に新たなブレークスルーがあり、GoogleリサーチがSODA 2024 Best Paper Awardを受賞

Google ブログは、無向グラフの最小カット問題を解決するための新しい研究を発表しました。

1996 年、アメリカのコンピュータ科学者 David R Karger と他の研究者は、論文「A new approach to」で最小カット問題に対する新しいアプローチを提案しました。 「最小カット問題」 驚くほどランダムなアルゴリズム Karger のアルゴリズムは理論コンピューター科学において非常に重要であり、大規模なグラフでの近似最小カット問題に特に適しています。

Karger のアルゴリズムは、時間 O (m log^3n) でグラフ内の最小カット ポイントを見つけることができます。この時間をほぼ線形時間と呼びます。これは、a を線形に乗算することを意味します。ポリログ係数。

Google が更新したばかりのブログで、以前に発表された論文「Deterministic Near-Linear Time Minimum Cut in Weighted Graphs」を紹介し、その研究により ACM-SIAM SODA24 が取得されました。最優秀論文賞受賞。この記事では、(線形に近い時間ではなく) ほぼ線形の時間で実行される新しいアルゴリズムについて詳しく説明します。このアルゴリズムは決定論的であり、正しい最小カットを確実に見つけることができます。これは、正しいかどうかが保証されていない、または適用可能なのみである以前のアルゴリズムを改善します。単純なグラフのアルゴリズムへ。おそらく、これは Karger の有名なランダム化アルゴリズム以来の最大の発見です。

• 論文のアドレス: https://arxiv.org/pdf/2401.05627.pdf
• 論文タイトル: 加重グラフにおける決定論的近線形時間最小カット

注: 最小カット問題 (ミニマム カットとも呼ばれます) は、グラフの接続性に関するものです。基本的な構造上の質問。一般に、ネットワークを切断する最も簡単な方法は何かということに焦点を当てています。グラフ理論では、すべてのエッジを削除することでネットワーク フロー グラフが接続されなくなる (つまり、2 つのサブグラフに分割される) エッジのセットをグラフのカットと呼び、グラフ上の最小のカットをグラフのカットと呼びます。最低限のカット。

^{# aグラフの最小カット（2つのエッジを含む）。}

#手法の紹介

最小カット問題については、 Karger は 1996 年に、高確率で最小カットを見つけることができるほぼ線形の時間ランダム アルゴリズムを開発しました。この研究により、すべてのカット サイズがほぼ保存される、より小さいグラフがあるという重要な洞察も得られました。

この発見は、より小さいグラフを入力として使用すると低速のアルゴリズムを実行でき、(サイズの点でより小さいグラフの場合) 実行時間は依然として線形に近いため、有益です。元の（大きい）グラフのサイズで。

#実際、最小カット問題に関する多くの構造的発見は、この方向に沿って行われています。

Google は、n 個のノードを持つグラフ G から開始して、論文「Randomized Approaches for Cuts and Flows in Capacitated Graphs」(Benzur 著) に基づいてこれを実行します。 Karger が提案したカット保存スパース化法は、エッジの少ないスパース加重グラフ G' を構築できることを証明しました。このグラフでは、ほぼすべてのカットのサイズが、対応するカットのサイズとほぼ同じです。元のグラフ G.

この概念は、次の例で説明できます。元のグラフは、単一のエッジで接続された 2 つの完全なグラフで構成されていますが、スパース化されたグラフのエッジは少なくなりますが、エッジはすべてのカットのサイズはほぼ維持されますが、重み付けがより重くなります。

このスパース グラフを構築するために、Benzur と Karger はエッジを個別にサンプリングする方法を採用しました。この方法では、グラフ G の各エッジはグラフ G' に含まれる一定の確率を持ち、G' の重みはサンプリング確率の逆数に従って増幅されます (たとえば、エッジの元の重みが次の場合)。 1 エッジは 10% の確率で含まれ、その重みは 10) に調整されます。この非常に単純な (ほぼ線形時間の) アプローチにより、高い確率でカット保存グラフのスパース化を構築できることがわかりました。

ただし、Karger アルゴリズムはモンテカルロ アルゴリズムです。つまり、出力が低い確率で誤っている可能性があり、そのかどうかを判断する既知の方法はありません。出力は正しいです。

# したがって、研究者たちは、ほぼ線形の時間決定論的アルゴリズムの未解決の問題を解決する方法を探求するために熱心に取り組んできました。カット保存グラフのスパース化の構築は Karger のアルゴリズムにおける唯一の確率的コンポーネントであるため、1 つのアプローチは、ほぼ線形時間でのスパース化の決定論的な構築 (非ランダム化とも呼ばれます) を見つけることです。

2015 年、河原林氏と Thorup 氏は、単純なグラフのグラフを見つけるという重要なマイルストーンを達成しました (つまり、ノードの各ペアとすべてのノードの間にエッジが 1 つだけ存在します)。エッジの重みは、決定論的近線形時間アルゴリズムの 1 つのグラフに等しい)。

研究は、最小カットと別の重要なグラフ構造 (「低コンダクタンス カット」と呼ばれる) との間に何らかの関係があるという重要なアイデアにつながります。このつながりは、後に一般的なエッジ加重グラフ上で Karger のアルゴリズムを非ランダム化するために重要であり、Google が新しいアルゴリズムを導き出すのに役立ちました。

最小カットと低コンダクタンスカットの位置合わせ

グラフカットSのコンダクタンスS のカット サイズと S の体積の比率として定義されます (S がカットの体積が小さい側であり、空ではないと仮定します)。ここで、S の体積は S 内のノードの次数です。

# 低コンダクタンスのカット S は、(体積に比べて) 少数のエッジだけが S を残りの部分に接続しているため、ネットワーク内のボトルネックを直感的に捉えます。グラフ。グラフのコンダクタンスは、グラフ内の任意のカットの最小コンダクタンスとして定義され、コンダクタンスが大きいグラフ (拡張グラフとも呼ばれます) は、内部にボトルネックがないため、よく接続されていると言われます。

^{この赤い点線は、CUT サイズが 2 で、小さい側 (底部) のボリュームが 24 であることを示しています。したがって、コンプタンスは次のようになります。 1/12、これもグラフのコンダクタンスです。}

Kawayabarashi と Thorup は、最小ノード次数が大きい単純なグラフでは、自明でない (つまり、どちらかの側に少なくとも 2 つのノードがある) 最小のグラフが存在することを観察しました。カットのコンダクタンスは低くなければなりません。この観察に基づいて、グラフを適切に接続されたクラスターに分割できる場合、すべてのクラスターがすべてのカットの片側に正確に存在する必要があるため、その分割はすべての非自明な最小カットと一致する必要があります。次に、各クラスターがノードに縮小され、元のグラフの重要な最小部分がすべてそのままの状態で、より小さなグラフが処理されます。

ただし、重み付きグラフの場合、上記の観察は当てはまらず、単純なグラフの場合に使用される同じ分割が、重要な最小カットと正確に一致しない可能性があります。

下の図に示すように、ジェイソン・リーは2021年に、この区分が依然として重要な最小カットとほぼ一致していることを観察しました。特に、自明ではない最小カット S の場合、S に類似したカット S' が存在し、S' はクラスターと一致します。 Jason Li はさらに、この分割の特性を利用して、カット保存グラフのスパース性の構築を効果的に非ランダム化できることを観察しました。

#Google が設計した新しいアルゴリズムは、最小カットのユースケースを定式化するパーティションを構築することを目的としています。 Google の調査は、Jason Li が以前の研究で使用した、より一般的な既製の方法よりも正確かつ迅速です。新しい研究では、精度を確保しながら実行時間を最適化し、最終的に最小カット問題に対するほぼ線形の時間決定論的アルゴリズムを達成しました。

^{参考リンク: https://research.google/blog/solve-the-minimum-cut-problem-for-undirected-graphs/}

以上が無向グラフの最小カット問題に新たなブレークスルーがあり、GoogleリサーチがSODA 2024 Best Paper Awardを受賞の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。