## DIMACS TR: 2006-17

## On the complexity of the exact weighted independent set problem for various graph classes

### Authors: Martin Milanic and Jerome Monnot

**
ABSTRACT
**

The exact weighted independent set problem (EWIS)
consists of determining whether a given weighted graph contains an
independent set whose weight equals a given integer M. We study
the problem of determining the complexity of the exact weighted
independent set problem, and its restricted version
EWIS_\alpha (where the independent set is required to
be of maximum size), for particular graph
classes. We prove that these problems are strongly
NP-complete for cubic bipartite graphs, and extend this result to a more
general setting. On the positive
side, we distinguish several graph classes where EWIS and
EWIS_\alpha can be solved in pseudo-polynomial time.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-17.ps.gz

DIMACS Home Page