Graphs with polynomially many minimal separators

DOI10.1016/J.JCTB.2021.10.003MaRDI QIDQ2664556zbMATH OpenOpenAlexFDO

Authors Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Nicolas Trotignon, Kristina Vušković, Stéphan Thomassé

Publication date 17 November 2021

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

induced subgraphminimal separatorprismpyramidthetaturtle

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs.

Recommendations

• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
• scientific article; zbMATH DE number 1420906
• On the number of minimal separators in graphs
• (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth

Cites work

• An introduction to clique minimal separator decomposition
• Finding induced subgraphs via minimal triangulations
• scientific article; zbMATH DE number 1420907 (Why is no real title available?)
• Independent set in P₅-free graphs in polynomial time
• Listing all potential maximal cliques of a graph
• On rank-width of (diamond, even-hole)-free graphs
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• Stable sets and graphs with no even holes
• Treewidth and minimum fill-in: Grouping the minimal separators

Cited in

(20)

• Minimal obstructions to ( , k )-polarity in cographs
• Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
• Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
• On the number of minimal separators in graphs
• Minimal separators in P₄-tidy graphs
• On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
• scientific article; zbMATH DE number 7217234 (Why is no real title available?)
• Detecting a Theta or a Prism
• scientific article; zbMATH DE number 1305094 (Why is no real title available?)
• On the number of minimal separators in graphs
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Bisimplicial separators
• Tree independence number. I. (Even hole, diamond, pyramid)-free graphs
• Taming graphs with no large creatures and skinny ladders
• Comparison of k-creature and t-critter
• Taming graphs with no large creatures and skinny ladders
• A polynomial bound on the number of minimal separators and potential maximal cliques in P₆-free graphs of bounded clique number
• Max weight independent set in graphs with no long claws: an analog of the Gyárfás' path argument
• Graphs with no long claws: an improved bound for the analog of the Gyárfás' path argument
• Exploring the closure operator for minimal a, b-separators: insights from Galois connections

This page was built for publication: Graphs with polynomially many minimal separators

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