A $(φ,ε)$-expander-decomposition of a graph $G$ (with $n$ vertices and $m$ edges) is a partition of $V$ into clusters $V_1,\ldots,V_k$ with conductance $Φ(G[V_i]) \ge φ$, such that there are $O(εm)$ inter-cluster edges. Such a decomposition plays a crucial role in many graph algorithms. [Agassy, Dorman, and Kaplan, ICALP 2023] (ADK) gave a randomized $\tilde{O}(m)$ time algorithm for computing a $(φ, φ\log^2 {n})$-expander decomposition. In this paper we generalize this result for a broader notion of expansion. Let $μ\in \mathbb{R}_{\ge 0 }^n$ be a vertex measure. A standard generalization of conductance of a cut $(S,\overline{S})$ is its $μ$-expansion $Φ^μ_G(S,\overline{S}) = |E(S,\overline{S})|/\min \{μ(S),μ(\overline{S})\}$, where $μ(S) = \sum_{v\in S} μ(v)$. We present a randomized $\tilde{O}(m)$ time algorithm for computing a $(φ, φ\log^2 {n}\cdot\frac{μ(V)}{m})$-expander decomposition with respect to $μ$-expansion. A substantial portion of the exposition is adapted from ADK, and this work serves as a convenient reference for generalized expander decomposition.
翻译：图 $G$（具有 $n$ 个顶点和 $m$ 条边）的 $(φ,ε)$-扩展图分解是将顶点集 $V$ 划分为若干簇 $V_1,\ldots,V_k$，使得每个簇的传导率满足 $Φ(G[V_i]) \ge φ$，且簇间边的数量为 $O(εm)$。此类分解在许多图算法中起着关键作用。[Agassy, Dorman, and Kaplan, ICALP 2023]（ADK）提出了一种随机化 $\tilde{O}(m)$ 时间算法，用于计算 $(φ, φ\log^2 {n})$-扩展图分解。本文将该结果推广至更广义的扩展性概念。设 $μ\in \mathbb{R}_{\ge 0 }^n$ 为顶点测度。割 $(S,\overline{S})$ 传导率的标准推广形式为其 $μ$-扩展性 $Φ^μ_G(S,\overline{S}) = |E(S,\overline{S})|/\min \{μ(S),μ(\overline{S})\}$，其中 $μ(S) = \sum_{v\in S} μ(v)$。我们提出一种随机化 $\tilde{O}(m)$ 时间算法，用于计算关于 $μ$-扩展性的 $(φ, φ\log^2 {n}\cdot\frac{μ(V)}{m})$-扩展图分解。本文的大部分论述借鉴自 ADK 的工作，旨在为广义扩展图分解提供一个便捷的参考框架。
相关内容
微信扫码咨询专知VIP会员