Alladi Ramakrishnan Hall

Graph Partitioning for Low Threshold-Rank and Semi-Random Instances

Rakesh Venkat

Hebrew University, Israel

Graph partitioning refers to a class of algorithmic problems that
ask for a partition of an input graph G into two or more parts, while
optimizing an objective function that measures the quality of the
partition. One natural criteria that is of both theoretical and practical
significance is that the cuts are 'sparse': they split the graph into
balanced parts with very few interactions across the parts. Although these
problems are usually NP-Hard to approximate (up to large factors) in the
general case, input graphs in practice often have some kind of structure
that could help one find better sparse cuts more efficiently. This presents
us with the natural question of designing algorithms that give better
guarantees or are more efficient for such input instances.

In this talk, we will mainly focus on how the Sparsest Cut problem can be
solved efficiently on a class of graphs called low threshold-rank graphs.
The Sparsest Cut objective measures the sparsity of a cut in terms of edges
going across the cut, normalized by the size of the partition. While the
best known approximation guarantee for this problem is $O(\sqrt{\log n})$ in
general, we show that one can do much better on graphs which already have a
'clustered' structure, using an efficient and intuitive algorithm. Our
algorithm also furnishes a generalization of a geometric theorem of
Goemans on embedding finite metric spaces into $\ell_1$.

In the latter part of the talk, we will briefly look at a natural
semi-random model of generating clustered input graphs where a better
objective is to consider the number of boundary vertices on the cut, as
opposed to edges across it. We will see an outline of how to exactly
recover a sparse vertex-cut in this setting using Semidefinite Programming.

(Based on joint works with Amit Deshpande, Prahladh Harsha, Anand Louis and
Yuval Rabani).