2012/04/20 by Tsz Chiu Kwok, Lap Chi Lau, Kwok, Tsz Chiu +1
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #VLSI and FPGA Design Techniques #cs.DS
paper · pdf · doi:10.48550/arxiv.1204.4666
arxiv created 2012/04/20 · openalex publication_date 2012/04/20 · arxiv updated 2012/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(√(ϕ/ε)) and vol(S) <= k1+ε 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(√(ϕ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.