Carving Lessons: How to Attack Hard Graph Problems

Christopher Homan
Department of Computer Science
Rochester Institute of Technology
cmh@cs.rit.edu

Abstract

Many hard problems on graphs can be solved if we "slice" off portions of the problem domain and/or are a little forgiving about being totally accurate. Case in point: The problem of finding a maximum independent set is not only NP-hard, but hard to even approximate within even a constant factor (meaning that if we had a fast algorithm for approximating max independent set then we could use this algorithm to solve ANY NP-complete problem, so probably no such algorithm exists). Nonetheless, we will show how to slice off portions of the domain so that, depending on how we slice, we get domains yielding fast exact or approximate max independent sets. These techniques apply to many other graph problems. The slices we get have a fairly nice characterization: if you draw the graphs in the slices and "squint" a little bit, they "look" like planar graphs or trees.

This talk describes work supported by a FEAD grant.


Colloquia Series page.