The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes |
| |
| Institution: | 1. University of Primorska, FAMNIT, Glagolja?ka 8, 6000 Koper, Slovenia;2. LAMSADE, Université Paris-Dauphine, Paris Cedex 16, France;1. LAMSADE UMR7243, PSL, Univ. Paris-Dauphine, France;2. Department of Mathematics, University of West Bohemia, European Centre of Excellence NTIS—New Technologies for the Information Society, P.O. Box 314, 306 14 Pilsen, Czech Republic;3. Le2I FRE2005, Université Bourgogne Franche-Comté, F-21000 Dijon, France;1. Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, ul. Banacha 2, 02-097 Warsaw, Poland;2. Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland;3. Faculty of Mathematics and Information Science, Warsaw University of Technology, Warsaw, Poland |
| |
| Abstract: | The exact weighted independent set (EWIS) problem consists in determining whether a given vertex-weighted graph contains an independent set of given weight. This problem is a generalization of two well-known problems, the NP-complete subset sum problem and the strongly NP-hard maximum weight independent set (MWIS) problem. Since the MWIS problem is polynomially solvable for some special graph classes, it is interesting to determine the complexity of this more general EWIS problem for such graph classes.We focus on the class of perfect graphs, which is one of the most general graph classes where the MWIS problem can be solved in polynomial time. It turns out that for certain subclasses of perfect graphs, the EWIS problem is solvable in pseudo-polynomial time, while on some others it remains strongly NP-complete. In particular, we show that the EWIS problem is strongly NP-complete for bipartite graphs of maximum degree three, but solvable in pseudo-polynomial time for cographs, interval graphs and chordal graphs, as well as for some other related graph classes. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
