A simple (2+\epsilon)-approximation algorithm for Split Vertex Deletion

MaRDI QIDQ6349698zbMATH OpenFDO

Authors Matthew Drescher, Samuel Fiorini, Tony Huynh

Publication date 23 September 2020

Mathematics Subject Classification ID

Perfect graphs (05C17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Abstract: A split graph is a graph whose vertex set can be partitioned into a clique and a stable set. Given a graph $G$ and weight function $w:V(G)omathbb{Q}_{geq0}$, the Split Vertex Deletion (SVD) problem asks to find a minimum weight set of vertices $X$ such that $G-X$ is a split graph. It is easy to show that a graph is a split graph if and only it it does not contain a $4$-cycle, $5$-cycle, or a two edge matching as an induced subgraph. Therefore, SVD admits an easy $5$-approximation algorithm. On the other hand, for every $delta>0$, SVD does not admit a $(2-delta)$-approximation algorithm, unless P=NP or the Unique Games Conjecture fails. For every $epsilon>0$, Lokshtanov, Misra, Panolan, Philip, and Saurabh recently gave a randomized $(2+epsilon)$-approximation algorithm for SVD. In this work we give an extremely simple deterministic $(2+epsilon)$-approximation algorithm for SVD.

This page was built for publication: A simple $(2+\epsilon)$-approximation algorithm for Split Vertex Deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6349698)