Finding Cut On Spectral-Hard Graphs Using Local Algorithms

We study the graph cut problem under local settings: algorithms have the constraint that its run time must be proportional to the set it outputs, instead of the entire graph. Quality of cut is measured under conductance metric. We experiment modified versions of Nibble algorithm in [1] and local pagerank algorithm in [2] on graphs that are designed to be “hard” on these algorithms.