Thursday, November 10, 2005
4:15 pm
B17 Upson Hall

Computer Science
Fall 2005

Uriel Feige
Weizmann Institute and Microsoft

Finding Small Balanced Separators in Graphs

A balanced separator in a graph is a set of vertices (or edges) whose removal separates the graph into roughly equal parts. The problem of finding the smallest balanced separator is of great practical interest in many contexts (such as the design of divide and conquer algorithms, or identifying bottlenecks in communication networks), but is NP-hard.

In this talk we present some algorithms that may be used in order to find small balanced separators in graphs. More generally, this will illustrate some of the approaches that are used by the "theory of computing" community when dealing with NP-hard problems. Hopefully we shall have time to touch upon approximation algorithms, fixed parameter algorithms, rigorous analysis of heuristics, and also on some negative results.