2012/09/12 by Andreas Brandstädt, Brandstädt, Andreas, Raffaele Mosca +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #cs.DM
paper · pdf · doi:10.48550/arxiv.1209.2512
arxiv created 2012/09/12 · openalex publication_date 2012/09/12 · arxiv updated 2012/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Maximum Weight Independent Set (MWIS) Problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated and most important problems on graphs, it is well known to be NP-complete and hard to approximate. The complexity of MWIS is open for hole-free graphs (i.e., graphs without induced subgraphs isomorphic to a chordless cycle of length at least five). By applying clique separator decomposition as well as modular decomposition, we obtain polynomial time solutions of MWIS for odd-hole- and dart-free graphs as well as for odd-hole- and bull-free graphs (dart and bull have five vertices, say a,b,c,d,e, and dart has edges ab,ac,ad,bd,cd,de, while bull has edges ab,bc,cd,be,ce). If the graphs are hole-free instead of odd-hole-free then stronger structural results and better time bounds are obtained.