






















We present a simple and faster algorithm for computing fair cuts on undirected graphs, a concept introduced in recent work of Li et al. (SODA 2023). Informally, for any parameter $ε>0$, a $(1+ε)$-fair $(s,t)$-cut is an $(s,t)$-cut such that there exists an $(s,t)$-flow that uses $1/(1+ε)$ fraction of the capacity of every edge in the cut. Our algorithm computes a $(1+ε)$-fair cut in $\tilde O(m/ε)$ time, improving on the $\tilde O(m/ε^3)$ time algorithm of Li et al. and matching the $\tilde O(m/ε)$ time algorithm of Sherman (STOC 2017) for standard $(1+ε)$-approximate min-cut. Our main idea is to run Sherman's approximate max-flow/min-cut algorithm iteratively on a (directed) residual graph. While Sherman's algorithm is originally stated for undirected graphs, we show that it provides guarantees for directed graphs that are good enough for our purposes.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。