2006-17: On the complexity of the exact weighted independent set problem for various graph classes

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