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)$-近似。该算法通过计算两个候选割 $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$ 相关联的总需求。
   • 约束： 算法求解 $G'$ 中的一个割，在满足总需求切断量上限 $K = \frac{4}{3}w(V)$ 的条件下最小化稀疏度。该约束确保了不会选择平凡割（$S=V$），并强制执行平衡划分。
   • 子程序： 此步骤利用了稀疏 $K$-有界割的 $\alpha$-近似算法。

2. 情况 2：大跨越需求 ($w(S^*, \bar{S}^*) \ge w(V)/3$)

   • 归约： 该问题被归约为**广义 $k$-多切（Generalized $k$-Multicut）**问题，随后进行 Max-Cut 步骤。
   • 技术： 首先，计算一个 $k$-多切，其中 $k = w(V)/3$，以分离大部分需求，从而产生一组连通分量。
   • 精炼： 这些连通分量构成了一个新完全图 $R$ 的顶点，其边权重代表分量之间的需求。随后在 $R$ 上计算 Max-Cut（使用贪心 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. 带需求的图划分：

   • 目标： 寻找一个最小成本的边集 $C$，使得 $G \setminus C$ 中的每个连通分量 $H$ 都满足 $w(H) \le \rho \cdot w(V)$。
   • 结果： 得到了一个 $O(\log n)$-双准则近似（bicriteria approximation）。算法返回一个成本为 $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）的最先进水平一致；对于树，则实现了常数因子近似。

论文最后提出了未来的研究方向，包括将框架扩展到超图（这需要一种新的超图电导率概念），以及探索与谱图理论的联系，特别是是否存在一个广义拉普拉斯算子能像经典切格不等式（Cheery inequality）那样与广义电导率相关联。