We give a 2-approximation algorithm for Cluster Vertex Deletion. This tight result matches the hardness lower bound. We obtain a new deterministic 7/3-approximation algorithm for Feedback Vertex Set in Tournaments. This result is based on the LP given by just one round of Sherali-Adams. We find a new, simpler deterministic (2 + epsilon)-approximation algorithm for Split Vertex Deletion. We give a 2-approximation algorithm for Claw-Free Vertex Deletion in triangle-free graphs. In the case of general graphs we prove that it is UGC-hard to obtain an approximation ratio lower than 3. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished
Identifer | oai:union.ndltd.org:ulb.ac.be/oai:dipot.ulb.ac.be:2013/333891 |
Date | 15 November 2021 |
Creators | Drescher, Matthew |
Contributors | Fiorini, Samuel, Cardinal, Jean, Joret, Gwenaël |
Publisher | Universite Libre de Bruxelles, Université libre de Bruxelles, Faculté des Sciences – Mathématiques, Bruxelles |
Source Sets | Université libre de Bruxelles |
Language | English |
Detected Language | English |
Type | info:eu-repo/semantics/doctoralThesis, info:ulb-repo/semantics/doctoralThesis, info:ulb-repo/semantics/openurl/vlink-dissertation |
Format | 3 full-text file(s): application/pdf | application/pdf | application/pdf |
Rights | 3 full-text file(s): info:eu-repo/semantics/openAccess | info:eu-repo/semantics/closedAccess | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0022 seconds