Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs

DOI10.1137/20m1333778OpenAlexW4391998821MaRDI QIDQ6203477

Maria Chudnovsky, Steéphan Thomassé, Michał Pilipczuk, Marcin Pilipczuk

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

approximation schememaximum weight independent sethereditary graph classesthree-in-a-tree

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The three-in-a-tree problem
• Some results on graphs without long induced paths
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Complement reducible graphs
• Stable sets in two subclasses of banner-free graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• 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
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Approximation algorithms for NP-complete problems on planar graphs
• Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
• On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs
• Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time

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