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/

Global: Zendy Tools annual

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

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We present a new, simple, algorithm for the local vertex connectivity problem(LocalVC) introduced by Nanongkai~et~al. [STOC'19]. Roughly, given anundirected unweighted graph $G$, a seed vertex $x$, a target volume $\nu$, anda target separator size $k$, the goal of LocalVC is to remove $k$ vertices`near' $x$ (in terms of $\nu$) to disconnect the graph in `local time', whichdepends only on parameters $\nu$ and $k$. In this paper, we present a simplerandomized algorithm with running time $O(\nu k^2)$ and correctness probability$2/3$.  Plugging our new localVC algorithm in the generic framework ofNanongkai~et~al. immediately lead to a randomized $\tilde O(m+nk^3)$-timealgorithm for the classic $k$-vertex connectivity problem on undirected graphs.($\tilde O(T)$ hides $\text{polylog}(T)$.) This is the first near-linear timealgorithm for any $4\leq k \leq \text{polylog} n$. Previous fastest algorithmfor small $k$ takes $\tilde O(m+n^{4/3}k^{7/3})$ time [Nanongkai~et~al.,STOC'19].  This work is inspired by the algorithm of Chechik~et~al. [SODA'17] forcomputing the maximal $k$-edge connected subgraphs. Forster and Yang [arXiv'19]has independently developed local algorithms similar to ours, and showed thatthey lead to an $\tilde O(k^3/\epsilon)$ bound for testing $k$-edge and -vertexconnectivity, resolving two long-standing open problems in property testingsince the work of Goldreich and Ron [STOC'97] and Orenstein and Ron [Theor.Comput. Sci.'11]. Inspired by this, we use local approximation algorithms toobtain bounds that are near-linear in $k$, namely $\tilde O(k/\epsilon)$ and$\tilde O(k/\epsilon^2)$ for the bounded and unbounded degree cases,respectively. For testing $k$-edge connectivity for simple graphs, the boundcan be improved to $\tilde O(\min(k/\epsilon, 1/\epsilon^2))$.

Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries