School of Technology and Computer Science Seminars

Finding Sparse Vertex Cuts in Semi-Random Instances

by Anand Louis (Indian Institute of Science, Bangalore)

Tuesday, April 16, 2019 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
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.
Organised by Prahladh Harsha