The exact weighted independent set problem in perfect graphs and related classes
Monnot, Jérôme; Milanic, Martin (2009), The exact weighted independent set problem in perfect graphs and related classes, Electronic notes in discrete mathematics, 35, p. 317322. http://dx.doi.org/10.1016/j.endm.2009.11.052
Type
Article accepté pour publication ou publiéDate
2009Journal name
Electronic notes in discrete mathematicsVolume
35Publisher
Elsevier
Pages
317322
Publication identifier
Metadata
Show full item recordAbstract (EN)
The exact weighted independent set (EWIS) problem consists in determining whether a given vertexweighted graph contains an independent set of given weight. This problem is a generalization of two wellknown problems, the NPcomplete subset sum problem and the strongly NPhard 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 pseudopolynomial time, while on some others it remains strongly NPcomplete. In particular, we show that the EWIS problem is strongly NPcomplete for bipartite graphs of maximum degree three, but solvable in pseudopolynomial time for cographs, interval graphs and chordal graphs, as well as for some other related graph classes.Subjects / Keywords
Graph theory; complexityRelated items
Showing items related by title and author.

Milanic, Martin; Monnot, Jérôme (2007) Document de travail / Working paper

Monnot, Jérôme; Milanic, Martin (2008) Chapitre d'ouvrage

Fritzilas, Epameinondas; Milanic, Martin; Monnot, Jérôme; RiosSolis, Yasmin Agueda (2009) Document de travail / Working paper

Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019) Communication / Conférence

Ries, Bernard; Monnot, Jérôme; Lozin, Vadim (2015) Article accepté pour publication ou publié