2 papers
math.CO2020
A simple -approximation algorithm for Split Vertex Deletion
Matthew Drescher, Samuel Fiorini, Tony Huynh
A split graph is a graph whose vertex set can be partitioned into a clique and a stable set. Given a graph and weight function , the Split Vert…
math.CO2020
A simple 7/3-approximation algorithm for feedback vertex set in tournaments
Manuel Aprile, Matthew Drescher, Samuel Fiorini +1
We show that performing just one round of the Sherali-Adams hierarchy gives an easy 7/3-approximation algorithm for the Feedback Vertex Set (FVST) problem in tournaments. This matc…