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

We study the {\em $k$-route} generalizations of various cut problems, themost general of which is \emph{$k$-route multicut} ($k$-MC) problem, wherein wehave $r$ source-sink pairs and the goal is to delete a minimum-cost set ofedges to reduce the edge-connectivity of every source-sink pair to below $k$.The $k$-route extensions of multiway cut ($k$-MWC), and the minimum $s$-$t$ cutproblem ($k$-$(s,t)$-cut), are similarly defined. We present variousapproximation and hardness results for these $k$-route cut problems thatimprove the state-of-the-art for these problems in several cases. (i) For {\em$k$-route multiway cut}, we devise simple, but surprisingly effective,combinatorial algorithms that yield bicriteria approximation guarantees thatmarkedly improve upon the previous-best guarantees. (ii) For {\em $k$-routemulticut}, we design algorithms that improve upon the previous-bestapproximation factors by roughly an $O(\sqrt{\log r})$-factor, when $k=2$, andfor general $k$ and unit costs and any fixed violation of the connectivitythreshold $k$. The main technical innovation is the definition of a new,powerful \emph{region growing} lemma that allows us to perform region-growingin a recursive fashion even though the LP solution yields a {\em differentmetric} for each source-sink pair. (iii) We complement these results by showingthat the {\em $k$-route $s$-$t$ cut} problem is at least as hard to approximateas the {\em densest-$k$-subgraph} (DkS) problem on uniform hypergraphs.

Improved Region-Growing and Combinatorial Algorithms for $k$-Route Cut Problems