
On the complexity of the exact weighted independent set problem
Milanic, Martin; Monnot, Jérôme (2007), On the complexity of the exact weighted independent set problem. https://basepub.dauphine.fr/handle/123456789/20748
View/ Open
Type
Document de travail / Working paperDate
2007Series title
Cahier du LAMSADESeries number
258Published in
Paris
Metadata
Show full item recordAuthor(s)
Milanic, MartinRutgers Center for Operations Research [RUTCOR]
Monnot, Jérôme

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
In this paper, we introduce the exact weighted independent set problem (EWIS), the problem of determining whether a given weighted graph contains an independent set of a given weight. Our motivation comes from the related exact perfect matching problem, whose computational complexity is still unknown. We determine the complexities of the EWIS problem and its restricted version EWIS (where the independent set is required to be of maximum size) for several graph classes. These problems are strongly NP-complete for cubic bipartite graphs; we also extend this result to a more general setting. On the positive side, we show that EWIS and EWIS can be solved in pseudo-polynomial time for chordal graphs, AT-free graphs, distance-hereditary graphs, circle graphs, graphs of bounded clique-width, and several subclasses of P5-free and fork-free graphs. In particular, we show how modular decomposition can be applied to the exact weighted independent set problem.Subjects / Keywords
exact weighted independent set; NP-complete; pseudo-polynomial algorithm; modular decompositionRelated items
Showing items related by title and author.
-
Monnot, Jérôme; Milanic, Martin (2008) Chapitre d'ouvrage
-
Monnot, Jérôme; Milanic, Martin (2009) Article accepté pour publication ou publié
-
Kim, Eun Jung; Milanic, Martin; Monnot, Jérôme; Picouleau, Christophe (2022) Article accepté pour publication ou publié
-
Ries, Bernard; Monnot, Jérôme; Lozin, Vadim (2015) Article accepté pour publication ou publié
-
Lozin, Vadim; Monnot, Jérôme; Ries, Bernard (2013) Communication / Conférence