The complexity of the exact weighted independent set problem
Monnot, Jérôme; Milanic, Martin (2008), The complexity of the exact weighted independent set problem, in Paschos, Vangelis, Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives: : 30th anniversary of the LAMSADE, Wiley : Hoboken (NJ), p. 393-432. http://dx.doi.org/10.1002/9780470611098.ch16
Book titleCombinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives: : 30th anniversary of the LAMSADE
Book authorPaschos, Vangelis
Number of pages515
MetadataShow full item record
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 / Keywordsbipartite graph; optimization problems; pseudo-polynomial time; practical importance; polynomial results
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 (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