A $(\phi,\epsilon)$-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 $\Phi(G[V_i]) \ge \phi$, such that there are at most $\epsilon m$ inter-cluster edges. Such a decomposition plays a crucial role in many graph algorithms. [ADK23] gave a randomized $\tilde{O}(m)$ time algorithm for computing a $(\phi, \phi\log^2 {n})$-expander decomposition. In this paper we generalize this result for a broader notion of expansion. Let $\mu \in {\mathbb{R}}_{\ge 0 }^n$ be a vertex measure. A standard generalization of conductance of a cut $(S,\bar{S})$ is its $\mu$-expansion $\Phi^{\mu}_G(S,\bar{S}) = |E(S,\bar{S})|/\min \mu(S)),\mu(\bar{S})\}$, where $\mu(S) = \sum_{v\in S} \mu(v)$. We present a randomized $\tilde{O}(m)$ time algorithm for computing a $(\phi, \phi \log^2 {n}\left(\frac{\mu(V)}{m}\right))$-expander decomposition with respect to $\mu$-expansion.
翻译：图 $G$（具有 $n$ 个顶点和 $m$ 条边）的 $(\phi,\epsilon)$-扩展图分解是将顶点集 $V$ 划分为若干簇 $V_1,\ldots,V_k$，使得每个簇的传导率 $\Phi(G[V_i]) \ge \phi$，且簇间边的数量不超过 $\epsilon m$。此类分解在许多图算法中起着关键作用。[ADK23] 提出了一种随机化 $\tilde{O}(m)$ 时间算法，用于计算 $(\phi, \phi\log^2 {n})$-扩展图分解。本文中，我们将该结果推广至更广义的扩展性概念。设 $\mu \in {\mathbb{R}}_{\ge 0 }^n$ 为顶点测度。割 $(S,\bar{S})$ 传导率的标准广义化形式为其 $\mu$-扩展性 $\Phi^{\mu}_G(S,\bar{S}) = |E(S,\bar{S})|/\min \{\mu(S),\mu(\bar{S})\}$，其中 $\mu(S) = \sum_{v\in S} \mu(v)$。我们提出一种随机化 $\tilde{O}(m)$ 时间算法，用于计算关于 $\mu$-扩展性的 $(\phi, \phi \log^2 {n}\left(\frac{\mu(V)}{m}\right))$-扩展图分解。
相关内容
微信扫码咨询专知VIP会员