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

The problem of computing the vertex expansion of a graph is an NP-hardproblem. The current best worst-case approximation guarantees for computing thevertex expansion of a graph are a $O(\sqrt{\log n})$-approximation algorithmdue to Feige, Hajiaghayi and Lee [SIAM J. Comp., 2008], and $O(\sqrt{OPT \logd})$ bound in graphs having vertex degrees at most $d$, due to Louis,Raghavendra and Vempala [FOCS 2013].  We study a natural semi-random model of graphs with sparse vertex cuts. Forcertain ranges of parameters, we give an algorithm to recover the plantedsparse vertex cut exactly. For a larger range of parameters, we give a constantfactor bi-criteria approximation algorithm to compute the graph's balancedvertex expansion. Our algorithms are based on studying a semidefiniteprogramming relaxation for the balanced vertex expansion of the graph.  In addition to being a family of instances that will help us to betterunderstand the complexity of the computation of vertex expansion, our model canalso be used in the study of community detection where only a few nodes fromeach community interact with nodes from other communities. There has been a lotof work on studying random and semi-random graphs with planted sparse edgecuts. To the best of our knowledge, our model of semi-random graphs withplanted sparse vertex cuts has not been studied before.

Semi-Random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery