Graph Partitioning with Demands: Generalized Conductance and its Applications

技術要約：需要を伴うグラフ分割：一般化されたコンダクタンスとその応用

問題定義
本研究は、一般的な需要モデルにおけるグラフ分割問題に対処するものである。入力はグラフ $G = (V, E, c, w)$ であり、$c: E \to \mathbb{N}$ は容量関数（エッジコスト）、$w: V \times V \to \mathbb{N}$ は頂点ペアの分離の重要性を表す需要関数である。

導入される中心的な問題は、**一般化コンダクタンス問題（Generalized Conductance Problem）**である。目的は、以下の量を最小化するカット $(S, \bar{S})$ を見つけることである：
$$\psi_w(S) = \frac{c(S, \bar{S})}{w(S, V) \cdot w(\bar{S}, V)}$$
ここで、$c(S, \bar{S})$ はカットを横切るエッジのコストであり、$w(X, V) = w(X) + w(X, \bar{X})$ は集合 $X$ に付随する総需要（内部および横断の両方）を表す。

著者らは、古典的な「最疎カット（Sparsest Cut）」（$c(S, \bar{S}) / w(S, \bar{S})$ を最小化する）は、一般的な需要設定における「バランス」を捉えるには不十分であると指摘している。例えば、完全にバランスの取れたカットがゼロの横断需要を持つ場合、最疎カットの値は無限大になるが、一般化されたコンダクタンスは有限かつ意味のある値となる。この指標は、分割統治戦略のような、バランスの取れた分割を必要とするアプリケーションにおいて極めて重要である。

手法およびアルゴリズムの枠組み
本論文は、一般グラフに対して $O(\log n)$ 近似を実現するために、二方向の還元戦略を用いて一般化コンダクタンス問題を解く手法を提案している。アルゴリズムは、より優れた目的関数値を持つ2つの候補カット $S_1$ と $S_2$ を計算し、それを返す。選択は、最適なカットを横切る需要の大きさ $w(S^*, \bar{S}^*)$ に依存する。

1. ケース1：横断需要が小さい場合 ($w(S^*, \bar{S}^*) \le w(V)/3$)

   • 還元： この問題は、**一般化された $K$-有界最疎カット（Generalized Sparsest $K$-Bounded Cut）**問題へと還元される。
   • 手法： すべての元の頂点に対してコストゼロのエッジを持つユニバーサル頂点 $r$ を追加することで、補助グラフ $G'$ を構築する。$r$ から任意の頂点 $u$ への需要は、元のグラフにおける $u$ に付随する総需要に設定される。
   • 制約： アルゴリズムは、総需要カットに対する上限 $K = \frac{4}{3}w(V)$ の条件下で、スパース性を最小化する $G'$ におけるカットを解く。この制約により、自明なカット（$S=V$）が選択されるのを防ぎ、バランスの取れた分割を強制する。
   • サブルーチン： このステップでは、スパース $K$-有界カットの $\alpha$-近似を利用する。

2. ケース2：横断需要が大きい場合 ($w(S^*, \bar{S}^*) \ge w(V)/3$)

   • 還元： この問題は、**一般化された $k$-マルチカット（Generalized $k$-Multicut）**問題への還元と、それに続く Max-Cut ステップへと還元される。
   • 手法： まず、$k = w(V)/3$ として、かなりの部分量の需要を分離する $k$-マルチカットを計算し、連結成分の集合を得る。
   • 洗練： これらの成分は、エッジの重みが成分間の需要を表す新しい完全グラフ $R$ の頂点を形成する。$R$ 上で Max-Cut を計算し（貪欲な2-近似を使用）、成分を2つのグループに分割する。
   • サブルーチン： このステップでは、一般化された $k$-マルチカットの $\beta$-近似を利用する。

サブ問題の解決
最終的な近似保証を得るために、本論文は **Räcke のカット・スパシファイア木分解（cut-sparsifier tree decomposition）**を採用している。

• 一般グラフは、多項式個の木の確率分布へと埋め込まれる。
• この埋め込みは、期待値において $O(\log n)$ の歪み内でカット値を保存する。
• アルゴリズムは、分布のサポート内にある各木上で、これらのサブ問題を最適に解く。
• 木の上では、これらの問題は単一エッジのカットを検討することで、多項式時間（多くの場合線形時間）で解くことが可能である。
• すべての木の中で最良の解を選択することで、一般グラフに対する $O(\log n)$ 近似を実現する。

主要な結果
本論文は、以下の近似保証を確立している：

1. 一般化コンダクタンス：

   • 一般グラフ： $O(\log n)$ 近似。
   • 木： $O(1)$ 近似（厳密に解求可能）。
   • 乗法的需要： $w(u, v) = \pi(u)\pi(v)$ である場合、保証は $O(\sqrt{\log n})$ に改善される。これは、問題を最小比率頂点カット（Min-Ratio Vertex Cut）問題に還元することで達成される。

2. 需要を伴うグラフ分割：

   • 目的： $G \setminus C$ におけるすべての連結成分 $H$ が $w(H) \le \rho \cdot w(V)$ を満たすような、最小コストのエッジ集合 $C$ を見つける。
   • 結果： $O(\log n)$ ビクリテリア近似が得られる。アルゴリズムは、コストが $O(\log n) \cdot \text{OPT}$ であり、かつ成分需要が $\eta \cdot w(V)$ 以下であることを保証するカットを返す（ここで $\rho < \eta < 1$）。
   • 乗法的需要／木： 保証はそれぞれ $O(\sqrt{\log n})$ および $O(1)$ に改善される。

3. 需要を伴う階層的クラスタリング：

   • 目的： グラフを再帰的に分割することにより、Dasgupta の目的関数（クラスターの需要で重み付けされたカットコストの総和）を最小化する。
   • 結果： グラフ分割アルゴリズムを反復的に適用することにより、一般グラフに対して $O(\log n)$ 近似、木に対して $O(1)$ 近似、および乗法的需要に対して $O(\sqrt{\log n})$ 近似を導出する。

意義と主張
著者らは、一般化コンダクタンスを、古典的な分割統治法における最疎カットと同様の、堅牢なアルゴリズム・プリミティブとして位置づけている。本研究の主な貢献は、この特定のパラメータの研究を開始したことであり、これは標準的なスパース性尺度と、一般的な需要設定におけるバランスの取れた分割の必要性ととの間の溝を埋めるものである。

本研究は、一般的な需要の複雑さにもかかわらず、問題が対数的な近似係数とともに計算可能であることを示している。また、これらの結果が階層的クラスタリングのようなダウンストリームのタスクにも拡張可能であることを明示的に主張しており、一般的な需要モデルにおけるこれらの問題に対して、初めて非自明な近似保証を提供している。著者らは、乗法的需要の場合、結果が一様最疎カット（Uniform Sparsest Cut）の最新技術と一致すること、そして木の場合には定数近似を達成していることを述べている。

最後に、本論文は今後の方向性として、ハイパーグラフへの拡張（新しいハイパーグラフ・コンダクタンスの概念が必要となる）や、スペクトルグラフ理論との関連（古典的なチェージャー不等式と同様に、一般化されたラプラシアンが一般化コンダクタンスに関連するかどうか）を提案して締めくくっている。