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

In the minimum $k$-cut problem, we want to find the minimum number of edgeswhose deletion breaks the input graph into at least $k$ connected components.The classic algorithm of Karger and Stein runs in $\tilde O(n^{2k-2})$ time,and recent, exciting developments have improved the running time to $O(n^k)$.For general, weighted graphs, this is tight assuming popular hardnessconjectures.  In this work, we show that perhaps surprisingly, $O(n^k)$ is not the rightanswer for simple, unweighted graphs. We design an algorithm that runs in time$O(n^{(1-\epsilon)k})$ where $\epsilon>0$ is an absolute constant, breaking thenatural $n^k$ barrier. This establishes a separation of the two problems in theunweighted and weighted cases.

Breaking the $n^k$ Barrier for Minimum $k$-cut on Simple Graphs