# The Ford-Fulkerson algorithm

Let me recall the standard scenario of flow optimization (for integer flows at least):

Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Consider a digraph $D$ with vertex set $V$ and arc set $A$. Fix two distinct vertices $s$ and $t$ of $D$, which we call the *source* and the *sink* (despite not requiring them to satisfy anything specific). A *capacity function* means a map $c : A \to \mathbb{N}$, which is thought of as assigning to each arc of $D$ the maximum amount of whatever it carries. Given a capacity function $c$, a *$c$-flow* (or *integer $c$-flow*) means a map $f : A \to \mathbb{N}$ satisfying the following two properties:

the

*capacity constraints*: $0 \leq f\left(a\right) \leq c\left(a\right)$ for any arc $a \in A$;the

*conservation constraints*: $\sum\limits_{\text{arcs } a \text{ having source } v} f\left(a\right) = \sum\limits_{\text{arcs } a \text{ having target } v} f\left(a\right)$ for any vertex $v \notin \left\{s,t\right\}$.

The *value* of a $c$-flow is defined to be the number \begin{equation}
\sum\limits_{\text{arcs } a \text{ having source } s} f\left(a\right) - \sum\limits_{\text{arcs } a \text{ having target } s} f\left(a\right) \\
= \sum\limits_{\text{arcs } a \text{ having target } t} f\left(a\right) - \sum\limits_{\text{arcs } a \text{ having source } t} f\left(a\right) .
\end{equation}

The Ford-Fulkerson algorithm (see, e.g., Section 8.2 in Jeremy L. Martin's *Lecture Notes on Algebraic Combinatorics*, or Section 4.3 in Lex Schrijver's *A Course in Combinatorial Optimization*, or Timon Thalwitzer's *Max-Flow Min-Cut*, or Section 1.8 in my Spring 2017 Math 5707 Lecture 16) constructs a $c$-flow with the maximum value. The algorithm proceeds by starting with the identically-$0$ flow and progressively improving it by finding a path in a certain (changing) digraph and modifying the flow along that path. The algorithm is not deterministic (it relies on finding *a* path in a digraph), but there are various ways of making it deterministic (such as taking the lexicographically smallest path, but there are also smarter ways; Section 4.4 in Schrijver's notes shows one).

# The question

Question 1.Is there any deterministic version of the Ford-Fulkerson algorithm that yields a maximum-value $c$-flow as a "tropical rational map" of $c$ ?

What do I mean by "tropical rational map"? For each $i$ and $k$, we let $\pi_i$ denote the map $\mathbb{N}^k \to \mathbb{N}$ that sends each $k$-tuple to its $i$-th entry. A *tropical rational function* is a map $\mathbb{N}^k \to \mathbb{N}$ that can be formed from the coordinate projections maps $\pi_i$ using addition, subtraction, minimum and maximum. (For instance, $\mathbb{N}^5 \to \mathbb{N},\ \left(a,b,c,d,e\right)\mapsto \min\left\{a,b\right\} + \max\left\{c,d\right\} - e$ is a tropical rational function... a rather important one in fact. So is $\mathbb{N}^2 \to \mathbb{N},\ \left(a,b\right) \mapsto \left|a+b\right| + \left|a-b\right|$.) A *tropical rational map* is a map $g : \mathbb{N}^k \to \mathbb{N}^\ell$ such that $\pi_i \circ g$ is a tropical rational function for each $i \in \ell$.

Any deterministic version of the Ford-Fulkerson algorithm can be regarded as a map $\mathbb{N}^A \to \mathbb{N}^A$ that sends any capacity function $c$ to a $c$-flow $f$. A priori, there is no reason for such a map even to be continuous (e.g., if it chooses between two parallel edges based on which one has bigger capacity, then it won't be continuous). Even for "reasonable" deterministic versions of the Ford-Fulkerson algorithm, I am not sure if they yield a tropical rational function (where we identify $\mathbb{N}^A$ with $\mathbb{N}^k$ for $k = \left|A\right|$). Indeed, if we allow capacities and flows to have non-integer values, then a "stupid" choice of augmenting paths in the Ford-Fulkerson algorithm leads to a never-terminating execution which doesn't even converge to a maximum-value flow; this doesn't happen with properly chosen augmenting paths, however.

# Motivation: The Hillman-Grassl algorithm

The following probably will mostly only make sense to the enumerative and algebraic combinatorialists. Here is why I suspect the Ford-Fulkerson algorithm to have a tropical-rational-function avatar.

The *Hillman-Grassl corresondence* (a bijection between reverse plane partitions of a given shape and arbitrary arrays of this shape; see, e.g., Section 5 of Alejandro Morales, Igor Pak, Greta Panova, *Hook formulas for skew shapes I. q-analogues and bijections* for a definition) is an algorithm that progressively decreases the entries of array by following something like "anti-augmenting paths". From this point of view, it is eerily similar to Ford-Fulkerson, apart from the fact that it keeps decreasing rather than increasing numbers. (It differs from Ford-Fulkerson also in what it records -- it's as if you wouldn't care about the maximum-value flow, but instead care about the augmenting paths you've used to build it.)

Question 2.Can we view the Hillman-Grassl correspondence as a Ford-Fulkerson algorithm for some directed graph, made deterministic according to some path-choosing rule?

Anyway, here is the motivation for the above question:

Proposition 3.The Hillman-Grassl correspondence is a tropical rational map.

Here is an *outline of a proof of Proposition 3* using a lot of handwaving (I don't really want to claim I'm sure of it). Recall how the Hillman-Grassl correspondence "disassembles" a reverse plane partition $\pi$ -- it works in multiple steps, where each step constructs a lattice path with north and east steps. In the form in which it is usually stated, the Hillman-Grassl algorithm decrements all entries of $\pi$ on this path by $1$; but we can modify this to make it decrement them by $r$ instead, where $r$ is the largest number they can be decremented by without breaking the reverse-plane-partition condition (explicitly: $r$ is the smallest difference of the form $\pi_{i,j} - \pi_{i-1,j}$ where $\left(i,j\right) \to \left(i,j+1\right)$ is an eastward step of the path). (This just corresponds to taking $r$ consecutive steps of the Hillman-Grassl algorithm.) Now, the crucial point is that there is a specific total order on all relevant lattice paths ("relevant" means that the path begins on a southern edge of the partition, and ends on an eastern one) such that the Hillman-Grassl algorithm uses the lattice paths in this order. (This is stronger than Lemma 4.2.3 in Bruce E. Sagan, *The Symmetric Group*, 2nd edition 2001 (errata); that lemma just says that the hooks that span the lattice paths appear in a specific order; but the rest is easy.) Thus, we can replace the algorithm by a "blind" version ("blind" in the sense that the lattice paths no longer depend on the entries of the reverse plane partition), which tries out all relevant lattice paths in this total order (there are only finitely many), decrementing each of them as much as possible. (Paths that don't appear in the original Hillman-Grassl algorithm will appear in this "blind" version, but the entries on them get decremented by $0$, so they don't make a difference.) So the "blind" version describes a tropical rational map.

Question 4.Is the inverse of the Hillman-Grassl correspondence (i.e., the map back from arrays to reverse plane partitions) a tropical rational map as well?

Note that I am aware of an "alternative" to the Hillman-Grassl correspondence (found by Pak, Hopkins and Sulzgruber independently), which is manifestly a tropical rational function (in both directions), obtained essentially by composing toggles. But Hillman-Grassl itself is not clearly of this form, and even the Greene-Kleitman invariants allegedly proven by Gansner in his thesis don't make that clear.

2more comments