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

DOI10.1007/S00373-014-1461-XMaRDI QIDQ497314zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Raffaele Mosca

Publication date 24 September 2015

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

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

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)

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.

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

Cites work

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

Cited in

(14)

• Maximum weight independent sets in hole- and co-chair-free graphs
• On the maximum weight independent set problem in graphs without induced cycles of length at least five
• 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 hole- and dart-free graphs
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-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
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
• Induced subgraphs of bounded treewidth and the container method

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)