Finding small sparse cuts by random walk

DOI10.1007/978-3-642-32512-0_52MaRDI QIDQ3167431zbMATH OpenOpenAlexFDO

Authors Tsz Chiu Kwok, Lap Chi Lau

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.4666

Mathematics Subject Classification ID

Connectivity (05C40) Random walks on graphs (05C81) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: 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 phi and vol(U) <= k, then there is a polynomial time algorithm to find a set S with conductance O(sqrt{phi/epsilon}) and vol(S) <= k^{1+epsilon} for any epsilon > 1/k. - If there is a subset U with conductance phi and vol(U) <= k, then there is a polynomial time algorithm to find a set S with conductance O(sqrt{phi ln(k)/epsilon}) and vol(S) <= (1+epsilon)k for any epsilon > 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.

Recommendations

• Finding sparse cuts locally using evolving sets
• Almost optimal local graph clustering using evolving sets
• Many sparse cuts via higher eigenvalues
• Using PageRank to Locally Partition a Graph
• Randomized approximation schemes for cuts and flows in capacitated graphs

Cited in

(6)

• Almost optimal local graph clustering using evolving sets
• Sparse Cut Projections in Graph Streams
• Density independent algorithms for sparsifying k-step random walks
• Deterministic approximation of random walks in small space
• Finding sparse cuts locally using evolving sets
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile

This page was built for publication: Finding small sparse cuts by random walk

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167431)