Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in H-Free Graphs

DOI10.1137/20M1333778MaRDI QIDQ6203477zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, Stéphan Thomassé

Publication date 28 February 2024

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

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

zbMATH Keywords

maximum weight independent setapproximation schemehereditary graph classesthree-in-a-tree

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 1187143 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• scientific article; zbMATH DE number 6783420 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
• Approximation algorithms for NP-complete problems on planar graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Complement reducible graphs
• Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time
• Independent set in \(P_5\)-free graphs in polynomial time
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• On maximal independent sets of vertices in claw-free graphs
• 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 approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
• Solving the weighted stable set problem in claw-free graphs via decomposition
• Some results on graphs without long induced paths
• Stable sets in two subclasses of banner-free graphs
• Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number
• The structure of claw-free graphs
• The three-in-a-tree problem
• \(H\)-colouring \(P_t\)-free graphs in subexponential time

This page was built for publication: Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs

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