##
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.