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

The All-Pairs Max-Flow problem has gained significant popularity in the lasttwo decades, and many results are known regarding its fine-grained complexity.Despite this, wide gaps remain in our understanding of the time complexity forseveral basic variants of the problem. In this paper, we aim to bridge this gapby providing algorithms, conditional lower bounds, and non-reducibilityresults. Our main result is that for most problem settings, deterministicreductions based on the Strong Exponential Time Hypothesis (SETH) cannot ruleout $n^{4-o(1)}$ time algorithms under a hypothesis called NSETH.  In particular, to obtain our result for the setting of undirected graphs withunit node-capacities, we design a new randomized $O(m^{2+o(1)})$ timecombinatorial algorithm, improving on the recent $O(m^{11/5+o(1)})$ timealgorithm [Huang et al., STOC 2023] and matching their $m^{2-o(1)}$ lower bound(up to subpolynomial factors), thus essentially settling the time complexityfor this setting of the problem.  More generally, our main technical contribution is the insight that $st$-cutscan be verified quickly, and that in most settings, $st$-flows can be shippedsuccinctly (i.e., with respect to the flow support). This is a key idea in ournon-reducibility results, and it may be of independent interest.

(Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow