A Simple and Fast Algorithm for Fair Cuts
摘要
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 \(\epsilon >0\) , a \((1+\epsilon )\) -fair (s, t)-cut is an (s, t)-cut such that there exists an (s, t)-flow that uses \(1/(1+\epsilon )\) fraction of the capacity of every edge in the cut. Our algorithm computes a \((1+\epsilon )\) -fair cut in \(\tilde{O}(m/\epsilon )\) time, improving on the \(\tilde{O}(m/\epsilon ^3)\) time algorithm of Li et al. and matching the \(\tilde{O}(m/\epsilon )\) time algorithm of Sherman (STOC 2017) for standard \((1+\epsilon )\) -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.