### DIMACS Computational and Mathematical Epidemiology Seminar Series

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.