Show simple item record

dc.contributor.authorMilanic, Martin
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2020-05-15T15:14:12Z
dc.date.available2020-05-15T15:14:12Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20748
dc.language.isoenen
dc.subjectexact weighted independent set
dc.subjectNP-complete
dc.subjectpseudo-polynomial algorithm
dc.subjectmodular decomposition
dc.subject.ddc003en
dc.titleOn the complexity of the exact weighted independent set problem
dc.typeDocument de travail / Working paper
dc.description.abstractenIn 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.
dc.publisher.cityParisen
dc.relation.ispartofseriestitleCahier du LAMSADE
dc.relation.ispartofseriesnumber258
dc.identifier.urlsitehttps://hal.archives-ouvertes.fr/hal-00917823
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidatenon
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2020-09-25T16:02:09Z


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record