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 Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this work, we resolve the query complexity of global minimum cut problemfor a graph by designing a randomized algorithm for approximating the size ofminimum cut in a graph, where the graph can be accessed through local querieslike {\sc Degree}, {\sc Neighbor}, and {\sc Adjacency} queries.  Given $\epsilon \in (0,1)$, the algorithm with high probability outputs anestimate $\hat{t}$ satisfying the following $(1-\epsilon) t \leq \hat{t} \leq(1+\epsilon) t$, where $m$ is the number of edges in the graph and $t$ is thesize of minimum cut in the graph. The expected number of local queries used byour algorithm is $\min\left\{m+n,\frac{m}{t}\right\}\mbox{poly}\left(\logn,\frac{1}{\epsilon}\right)$ where $n$ is the number of vertices in the graph.Eden and Rosenbaum showed that $\Omega(m/t)$ many local queries are requiredfor approximating the size of minimum cut in graphs. These two results togetherresolve the query complexity of the problem of estimating the size of minimumcut in graphs using local queries.  Building on the lower bound of Eden and Rosenbaum, we show that, for all $t\in \mathbb{N}$, $\Omega(m)$ local queries are required to decide if the sizeof the minimum cut in the graph is $t$ or $t-2$. Also, we show that, for any $t\in \mathbb{N}$, $\Omega(m)$ local queries are required to find all the minimumcut edges even if it is promised that the input graph has a minimum cut of size$t$. Both of our lower bound results are randomized, and hold even if we canmake {\sc Random Edge} query apart from local queries.

Query Complexity of Global Minimum Cut