




















We study the problem of finding a small sparse cut in an undirected graph. Given an undirected graph G=(V,E) and a parameter k <= |E|, the small sparsest cut problem is to find a subset of vertices S with minimum conductance among all sets with volume at most k. Using ideas developed in local graph partitioning algorithms, we obtain the following bicriteria approximation algorithms for the small sparsest cut problem: - If there is a subset U with conductance φand vol(U) <= k, then there is a polynomial time algorithm to find a set S with conductance O(\sqrt{φ/ε}) and vol(S) <= k^{1+ε} for any ε> 1/k. - If there is a subset U with conductance φand vol(U) <= k, then there is a polynomial time algorithm to find a set S with conductance O(\sqrt{φln(k)/ε}) and vol(S) <= (1+ε)k for any ε> 2ln(k)/k. These algorithms can be implemented locally using truncated random walk, with running time almost linear to the output size. This provides a local graph partitioning algorithm with a better conductance guarantee when k is sublinear.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。