Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems

DOI10.1145/3389338MaRDI QIDQ5888942zbMATH OpenOpenAlexFDO

Authors Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi

Publication date 26 April 2023

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3389338

zbMATH Keywords

\(\mathcal{F}\)-vertex deletionapproximation algorithmbalanced separatorschordal graphsdistance hereditary graphsplanar \(\mathcal{F}\)-minor-free graphs

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• A constant-factor approximation for weighted bond cover
• Hitting forbidden minors: approximation and kernelization
• Approximation and kernelization for chordal vertex deletion

Cited in

(8)

• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• Polynomial-time data reduction for weighted problems beyond additive goal functions
• A polynomial kernel for distance-hereditary vertex deletion
• Constant factor approximation for tracking paths and fault tolerant feedback vertex set
• Constant factor approximation for tracking paths and fault tolerant feedback vertex set
• Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
• Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
• A constant-factor approximation for weighted bond cover

This page was built for publication: Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems

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