Title: Unbalanced Graph Cuts
Speaker: Martin Pal, DIMACS
Date: February 21, 2005 2:30 - 3:45 pm**
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We consider the following problem, motivated by epidemiology: given a (directed or undirected) graph, a specific source vertex s and a budget B, we want to find a cut whose capacity is at most B, that minimizes the number of vertices in the component containing the source vertex. We can think of the source as a "bad" vertex spreading a disease, and our goal is, with a limited number of vaccines available, ensure that the disease is contained, while minimizing the number of people who get infected.
We can look at both edge and vertex cut versions of the problem, as well as allow capacities on edges and weights on nodes to model the notion of a "target" sub-population we wish to protect. I will show that the problem of finding a minimum-size bounded-capacity cut (MinSBCC) is NP-hard, and give some approximation algorithms: a bicriteria approximation algorithm that may violate the budget B by a factor of 2, while delivering a cut that leaves at most twice as many people unprotected in comparison to the optimum cut, and a polynomial time approximation scheme on graphs of bounded treewidth. There are always great open questions, such as what happens if you consider more accurate models of disease spread, or incorporate time into the model.
This is joint work with Ara Hayrapetyan, David Kempe and Zoya Svitkina.