 License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.80
URN: urn:nbn:de:0030-drops-124879
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12487/
 Go to the corresponding LIPIcs Volume Portal

### A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion

 pdf-format:

### 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.

### BibTeX - Entry

```@InProceedings{lokshtanov_et_al:LIPIcs:2020:12487,
author =	{Daniel Lokshtanov and Pranabendu Misra and Fahad Panolan and Geevarghese Philip and Saket Saurabh},
title =	{{A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion}},
booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages =	{80:1--80:16},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-138-2},
ISSN =	{1868-8969},
year =	{2020},
volume =	{168},
editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 