Maximum weight independent sets in odd-hole-free graphs without dart or without bull

DOI10.1007/S00373-014-1461-XzbMATH Open1321.05178arXiv1209.2512OpenAlexW1972095231MaRDI QIDQ497314FDOQ497314

Authors: Andreas Brandstädt, Raffaele Mosca 

Publication date: 24 September 2015

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1209.2512

Recommendations

• Maximum weight independent sets in hole- and dart-free graphs
• Maximum weight independent sets in hole- and co-chair-free graphs
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• Maximum weight independent sets in classes related to claw-free graphs
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs

zbMATH Keywords

modular decompositionmaximum weight independent setpolynomial time algorithmclique separatorshole-free graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Cites Work

• Graph Classes: A Survey
• Modular decomposition and transitive orientation
• Title not available (Why is that?)
• The structure of bull-free graphs II and III -- a summary
• The strong perfect graph theorem
• Recognizing Berge graphs
• Stability number of bull- and chair-free graphs
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• Recognizing weakly triangulated graphs by edge separability
• Title not available (Why is that?)
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Maximum weight independent sets in hole- and dart-free graphs
• Rose window graphs
• Algorithms for weakly triangulated graphs
• Stability number of bull- and chair-free graphs revisited
• Independence and irredundance in \(k\)-regular graphs
• Maximum weight independent sets in hole- and co-chair-free graphs
• On independent vertex sets in subclasses of apple-free graphs
• Finding large holes
• Improved algorithms for weakly chordal graphs
• A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• A characterization of some graph classes with no long holes
• Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
• On the vertex packing problem
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Recognizing Dart-Free Perfect Graphs
• Odd Hole Recognition in Graphs of Bounded Clique Size
• On the structure of bull-free perfect graphs

Cited In (14)

• On the maximum weight independent set problem in graphs without induced cycles of length at least five
• Maximum weight independent sets in hole- and co-chair-free graphs
• Graphs without large apples and the maximum weight independent set problem
• Independent sets in some classes of \(S_{i,j,k}\)-free graphs
• The maximum weight stable set problem in (\(P_6\), bull)-free graphs
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• Maximum weight independent sets in hole- and dart-free graphs
• One-three join: a graph operation and its consequences
• 2-divisibility of some odd hole free graphs
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• Independent Sets in Classes Related to Chair-Free Graphs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Induced subgraphs of bounded treewidth and the container method
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs

This page was built for publication: Maximum weight independent sets in odd-hole-free graphs without dart or without bull

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q497314)