English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

A split graph is a graph whose vertex set can be partitioned into a cliqueand a stable set. Given a graph $G$ and weight function $w: V(G) \to\mathbb{Q}_{\geq 0}$, the Split Vertex Deletion (SVD) problem asks to find aminimum weight set of vertices $X$ such that $G-X$ is a split graph. It is easyto 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, unlessP=NP or the Unique Games Conjecture fails.  For every $\epsilon >0$, Lokshtanov, Misra, Panolan, Philip, and Saurabhrecently gave a randomized $(2+\epsilon)$-approximation algorithm for SVD. Inthis work we give an extremely simple deterministic$(2+\epsilon)$-approximation algorithm for SVD.

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