Warm-starting Push-Relabel

This paper studies the push-relabel algorithm with warm-starts for the max-flow problem. Despite its empirical efficiency, the standard analysis of the algorithm is known to result in a somewhat pessimistic bound of $O(n^2m)$. The current paper considers a situation where the algorithm takes a predicted pseudo-flow $\hat f$ and has shown that the running time can be bounded by $O(n^2\eta)$, where $\eta$ is a prediction error that is at most $\\| \hat f - f^* \\|\_1$ for an optimal flow $f^*$. En route to this result, the authors have also shown that push-relabel with the gap-relabeling heuristic fed with a cut-saturating pre-flow (Algorithm 1) enjoys the same error-dependent bound. Overall, the algorithm converts $\hat f$ into a cut-saturating pseudo-flow $f$ in $O(n^2\eta)$ time (Algorithm 5), updates $f$ in $O(n^2\eta)$ time so that the $t$-side ($s$-side) has no excess (deficit) nodes (Algorithm 2), and fixes excess (deficit) in the $t$-side ($s$-side) with Algorithm 1. The main technical novelty lies in the update step, which swaps excess and deficit nodes between $t$- and $s$-sides. Finally, experiments on image-segmentation datasets confirm the effectiveness of push-relabel with warm-starts, compared with cold-start push-relabel and cold- and warm-start Ford--Fulkerson.

Authors provide the first theoretical guarantees for the Push-Relabel (PR) algorithm coupled with the gap relabeling heuristic, to address max flow problems, while using an arbitrary (pseudo-flow) initialization such as a predicted flow. The main result relates to proving a worse case complexity of $O(\eta * n^2)$ for their algorithm given a predicted pseudo-flow with error $\eta$ (cf Def 1) on the network with $n$ nodes. Finally, they validate empirically their theoretical analysis while showing the relevance of their algorithm compared to well-known competitive algorithms.

This paper provides the running-time complexity analysis for warm-start Push-Relabel algorithm for the fundamental max-flow/min-cut problem. In particular, they study learning-augmented version of the Push-Relabel algorithm, where the algorithm can start from a pseudo-flow with error bounded by $\eta$. The main result is that a minimum cut can be found in time $O(\eta\cdot n^2)$, which improves upon the $O(n^2 m)$ runtime of basic Ford Fulkerson.

This paper propose and analyzes a warm starting scheme for the classical push-relabel algorithm for max-flow problems. The basic approach is to convert the warm-starting flow into a cut-saturating flow, at which point a clever push-relabel scheme is used to ensure that the source-side of the cut has only excess flow while the sink side of the cut has only flow deficits. This immediately yields a min-cut and is easily transformed into a max flow solution. The authors compare their approach with warm-starting methods for the Ford-Folkerson algorithm, which they show is less efficient in practice.

We thank the reviewers for their careful reading of our paper! We are glad they agree that warm-starting the push relabel algorithm to find a max flow/min cut is an interesting theoretical question with potentially useful practical applications.

Please see comments on questions brought up by several reviewers here, and individual replies below each review. Also, the visualization requested by Reviewer oTzZ is attached.

Comparing to work on warm-starting Ford Fulkerson: Recall the cold-start running time of Edmonds Karp is $O(m^2n)$, while cold-start PR is $O(mn^2)$. Previous work in [Davies, et al. 2023] shows that warm-start FF has running time $O(m ||\hat{f}-f^*||_1)$, while we show that warm-start PR has running time $O(n^2 \eta) < O(n^2 ||\hat{f}-f^*||_1)$. Our theoretical result may not always be better than warm-start FF, depending on how close $\eta$ and $||\hat{f}-f^*||_1$ are (note Push-Relabel is less affected by sparsity then Edmonds Karp). Overall, this is not a weakness to our analysis, but is an artifact of the community’s lack of understanding on why push-relabel performs so much better in practice than its theoretical bounds guarantee.

We further explain the theoretical importance of our result. Improving our theoretical understanding of algorithms that do well in practice (like Push-Relabel) is one of the pillars of the field of beyond worst-case analysis (most famously, the smoothed analysis to analyze the Simplex Method, though see also Tim Roughgarden's book and lectures on beyond worst-case analysis). Researchers have long suspected that there should be a way to parameterize instances or use practical heuristics to justify why Push Relabel is so much better in practice, and tools are actively being developed with a hope of eventually achieving this goal (e.g., the line of work by J. Diakonikolas and Song). Our work identifies that there is a monotonic property in the cuts when Push-Relabel is implemented with the gap relabeling heuristic that directly results in faster runtime when the value of the max flow/min cut is small (see our Corollary 1). While such a result was known for Ford-Fulkerson, this was NOT known for Push-Relabel prior to our work. We speculate this monotonic property may have further theoretical importance in improving Push-Relabel analyses on more general classes of networks.

We are happy to add this discussion to the main body of the paper in the technical contributions section.

Computing $\eta$: The error metric $\eta$, when unknown a priori, is computed synchronously while transforming the given pseudo-flow to be cut-saturating, and given as input to Algorithm 2 afterwards. This procedure is described in A.3, lines 476-491. The doubling search finds $\eta$ “for free” (the found $\eta$ is at most twice the true error in Definition 1) without additional running time complexity for the overall algorithm. Note that the doubling trick is a standard tool in algorithm design for coping with unknown values.

We agree with a reviewer that more discussion on computing $\eta$ should be in the main body, hence we propose making the following changes to clarify how $\eta$ is found and used. In Appendix A.3, we will explicitly add pseudocode to formally describe the doubling search procedure for $\eta$: initialize with $\eta$=1; in each iteration call Algorithm 5 as a subroutine that takes $\eta$ as input and tries to augment the pseudo-flow by value $\eta$; if successful, then $\eta$ doubles. The procedure terminates upon saturating the flow, i.e., Algorithm 5 finds a $s-t$ cut instead of cutting the edge $(s^*, s)$. The new pseudocode, along with Algorithm 5, completes the pre-process algorithm for warm-start flow initialization, and also outputs a correct error bound $\eta$ that is used in subsequent push relabel operations. In the main body before Algorithm 2 is stated, we will clarify that $\eta$, if unknown, has to be found via the algorithmic approaches in A.3 and add a short summary on the doubling search procedure.

Empirical Values of $\eta$: Many reviewers are interested in the computation of $\eta$ in practice and its value in our image segmentation experiments. The doubling procedure in A.3 is an option, but one can use other surrogates for $\eta$ as long as they prove an effective upper bound on the error. In our experiments, $\eta$ is estimated by computing both the total excess/deficit, and the $\sigma$ (in the “$\sigma$ away from being cut saturating” notion in Line 75) by using the old cut in the previous image in the sequence. Typically this is a loose bound, but it suffices for our purpose.

We show the error metrics on a sequence of 10 images of size 60X60 from the group DOG. The average total excess/deficit accounts for 69% of the real min cut, whereas the $\sigma$, computed a posteriori using the min cut, accounts for about 23%. The results should be read together with the measured error metric value in [Davies, et al., 2023] under the same experiment designs. Our $\eta$ is not negligible but still boosts Push-Relabel's performance with warm-starting, despite the dependency of the theoretical bound on $\eta$. This is typical --- algorithms in practice often run much faster than their theoretical bounds. In [Davies, et al. 2023], the empirical prediction errors (see, e.g., Table 5 in the Appendix) are at similar levels, and can be even higher than the max-flow value. As is discussed in their paper, the savings in running time results from the augmenting paths routing excess to deficit being much shorter than the source-sink augmenting paths; hence the performance goes beyond the theoretical O(m \eta). Excesses/deficits are big in our setting, too, but the initialized pseudo-flow is already quite close to being cut-saturating. Perhaps this explains the speed-up we obtain.

Dear authors -- thank you for an interesting well-written paper that provides new theoretical insights into the surprisingly good performance of warm-starting for push-relabel algorithms for max-flow. While the topic of the paper is specialized to a fairly narrow area -- the reviewers all enjoyed the paper, and the analysis makes a tangible contribution to the "observed" (beyond worst case) behavior of combinatorial algorithms . We hope that you'll be able to incorporate reviewer's suggestions in the final version (e.g. incorporating more detailed description of computing eta). I recommend the paper for acceptance.