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
TypeDocument de travail / Working paper
Series titleCahier du LAMSADE
MetadataShow full item record
Rutgers Center for Operations Research [RUTCOR]
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 / Keywordsexact weighted independent set; NP-complete; pseudo-polynomial algorithm; modular decomposition
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