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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12487/
Go to the corresponding LIPIcs Volume Portal

Lokshtanov, Daniel ; Misra, Pranabendu ; Panolan, Fahad ; Philip, Geevarghese ; Saurabh, Saket

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

pdf-format:
LIPIcs-ICALP-2020-80.pdf (0.7 MB)

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},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12487},
  URN =		{urn:nbn:de:0030-drops-124879},
  doi =		{10.4230/LIPIcs.ICALP.2020.80},
  annote =	{Keywords: Approximation Algorithms, Graph Algorithms, Split Vertex Deletion}
}

Keywords: Approximation Algorithms, Graph Algorithms, Split Vertex Deletion
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI