Abstract: Graph partitioning problems are a central topic of research in the study of algorithms and complexity theory. One of the central problems studied in this field is the problem of computing the set having the least vertex expansion. For a graph G, the vertex expansion of a set S of vertices is defined as the ratio of the number of vertices in the boundary of S to the size of S. Computing the set of vertices having the least vertex expansion is an NP-hard problem.
In this talk, I'll describe a natural semi-random model of graphs with sparse vertex cuts, and present approximation algorithms for the problem of computing the sparsest vertex cut in this model. Based on joint work with Rakesh Venkat.
