Finding Small Sparse Cuts Locally by Random Walk

Details Finding Small Sparse Cuts Locally by Random Walk Finding Small Sparse Cuts Locally by Random Walk

2012-04-20

arxiv.org/abs/1204.4666v1

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Finding Small Sparse Cuts Locally by Random Walk does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding Small Sparse Cuts Locally by Random Walk, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding Small Sparse Cuts Locally by Random Walk will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-6037