A (2+)-factor approximation algorithm for split vertex deletion

DOI10.4230/LIPICS.ICALP.2020.80MaRDI QIDQ6842492zbMATH OpenFDO

Authors Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, Saket Saurabh

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.80

zbMATH Keywords

approximation algorithmsgraph algorithmssplit vertex deletion

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• 2-Approximating Feedback Vertex Set in Tournaments
• \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
• A 7/3-approximation for feedback vertex sets in tournaments
• A linear-time approximation algorithm for the weighted vertex cover problem
• An approximation algorithm for feedback vertex sets in tournaments
• Approximate association via dissociation
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 219267 (Why is no real title available?)
• The node-deletion problem for hereditary properties is NP-complete
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

This page was built for publication: A \((2+\varepsilon)\)-factor approximation algorithm for split vertex deletion

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