2026-07-26T21:06:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12487 2024-03-06T10:50:16Z ddc:004 open_access

A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion Lokshtanov, Daniel Misra, Pranabendu Panolan, Fahad Philip, Geevarghese Saurabh, Saket Approximation Algorithms Graph Algorithms Split Vertex Deletion 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Lokshtanov and Pranabendu Misra and Fahad Panolan and Geevarghese Philip and Saket Saurabh 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.80 urn:nbn:de:0030-drops-124879 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.80 eng https://creativecommons.org/licenses/by/3.0/legalcode