Induced subgraphs of bounded treewidth and the container method

DOI10.1137/20M1383732MaRDI QIDQ6550989zbMATH OpenFDO

Authors Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski, Paul Seymour

Publication date 5 June 2024

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/20M1383732

zbMATH Keywords

\(P_t\)-free graphsfeedback vertex setindependent setlong-hole-free graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the maximum weight independent set problem in graphs without induced cycles of length at least five
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• Large induced subgraphs via triangulations and CMSO
• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs

Cites work

• A Linear Recognition Algorithm for Cographs
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Complexity of Finding Embeddings in a k-Tree
• Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
• Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
• Finding induced subgraphs via minimal triangulations
• Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time
• scientific article; zbMATH DE number 3919840 (Why is no real title available?)
• scientific article; zbMATH DE number 7788454 (Why is no real title available?)
• Hypergraph containers
• Independent feedback vertex set for P₅-free graphs
• Independent set in P₅-free graphs in polynomial time
• Independent sets of maximum weight in apple-free graphs
• Large Induced Subgraphs via Triangulations and CMSO
• Listing all potential maximal cliques of a graph
• Maximum weight independent sets in hole- and co-chair-free graphs
• Maximum weight independent sets in hole- and dart-free graphs
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• On cycle transversals and their connected variants in the absence of a small linear forest
• On the maximum weight independent set problem in graphs without induced cycles of length at least five
• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs
• Quasi-polynomial-time algorithm for independent set in P_t-free graphs via shrinking the space of induced paths
• Reducibility among combinatorial problems
• Sparse induced subgraphs in P₆-free graphs
• The ellipsoid method and its consequences in combinatorial optimization
• The strong perfect graph theorem
• Treewidth and minimum fill-in: Grouping the minimal separators
• Upper bounds to the clique width of graphs

Cited in

(2)

• Tree decompositions meet induced matchings: beyond max weight independent set
• Sparse induced subgraphs in P₇-Free graphs of bounded clique number

This page was built for publication: Induced subgraphs of bounded treewidth and the container method

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