• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
cahier_258.pdf (507.2Kb)
Type
Document de travail / Working paper
Date
2007
Series title
Cahier du LAMSADE
Series number
258
Published in
Paris
Metadata
Show full item record
Author(s)
Milanic, Martin
Rutgers Center for Operations Research [RUTCOR]
Monnot, Jérôme cc
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 decomposition

Related items

Showing items related by title and author.

  • Thumbnail
    The complexity of the exact weighted independent set problem 
    Monnot, Jérôme; Milanic, Martin (2008) Chapitre d'ouvrage
  • Thumbnail
    The exact weighted independent set problem in perfect graphs and related classes 
    Monnot, Jérôme; Milanic, Martin (2009) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and algorithms for constant diameter augmentation problems 
    Kim, Eun Jung; Milanic, Martin; Monnot, Jérôme; Picouleau, Christophe (2022) Article accepté pour publication ou publié
  • Thumbnail
    On the maximum independent set problem in subclasses of subcubic graphs 
    Ries, Bernard; Monnot, Jérôme; Lozin, Vadim (2015) Article accepté pour publication ou publié
  • Thumbnail
    On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs 
    Lozin, Vadim; Monnot, Jérôme; Ries, Bernard (2013) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo