dc.contributor.author | Lokshtanov, Daniel | |
dc.contributor.author | Misra, Pranabendu | |
dc.contributor.author | Panolan, Fahad | |
dc.contributor.author | Philip, Geevarghese | |
dc.contributor.author | Saurabh, Saket | |
dc.date.accessioned | 2021-07-09T07:13:34Z | |
dc.date.available | 2021-07-09T07:13:34Z | |
dc.date.created | 2021-02-17T13:05:27Z | |
dc.date.issued | 2020 | |
dc.identifier.isbn | 978-3-95977-138-2 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/2763990 | |
dc.description.abstract | In the Split Vertex Deletion (SVD) problem, the input is an n-vertex undirected graph G and a weight function w: V(G) → ℕ, and the objective is to find a minimum weight subset S of vertices such that G-S is a split graph (i.e., there is bipartition of V(G-S) = C ⊎ I such that C is a clique and I is an independent set in G-S). This problem is a special case of 5-Hitting Set and consequently, there is a simple factor 5-approximation algorithm for this. On the negative side, it is easy to show that the problem does not admit a polynomial time (2-δ)-approximation algorithm, for any fixed δ > 0, unless the Unique Games Conjecture fails. We start by giving a simple quasipolynomial time (n^O(log n)) factor 2-approximation algorithm for SVD using the notion of clique-independent set separating collection. Thus, on the one hand SVD admits a factor 2-approximation in quasipolynomial time, and on the other hand this approximation factor cannot be improved assuming UGC. It naturally leads to the following question: Can SVD be 2-approximated in polynomial time? In this work we almost close this gap and prove that for any ε > 0, there is a n^O(log 1/(ε))-time 2(1+ε)-approximation algorithm. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Schloss Dagstuhl – Leibniz Center for Informatics | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright the authors | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | https://doi.org/10.4230/LIPIcs.ICALP.2020.80 | |
dc.identifier.cristin | 1890877 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.pagenumber | 80:1-80:16 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics. 2020, 168, 80. | en_US |
dc.source.volume | 168 | en_US |