Lokshtanov, Daniel ;
Misra, Pranabendu ;
Panolan, Fahad ;
Philip, Geevarghese ;
Saurabh, Saket
A (2 + ε)Factor Approximation Algorithm for Split Vertex Deletion
Abstract
In the Split Vertex Deletion (SVD) problem, the input is an nvertex 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 GS is a split graph (i.e., there is bipartition of V(GS) = C ⊎ I such that C is a clique and I is an independent set in GS). This problem is a special case of 5Hitting Set and consequently, there is a simple factor 5approximation 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 2approximation algorithm for SVD using the notion of cliqueindependent set separating collection. Thus, on the one hand SVD admits a factor 2approximation 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 2approximated 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:180:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12487},
URN = {urn:nbn:de:0030drops124879},
doi = {10.4230/LIPIcs.ICALP.2020.80},
annote = {Keywords: Approximation Algorithms, Graph Algorithms, Split Vertex Deletion}
}
29.06.2020
Keywords: 

Approximation Algorithms, Graph Algorithms, Split Vertex Deletion 
Seminar: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Issue date: 

2020 
Date of publication: 

29.06.2020 