Is the Ford-Fulkerson algorithm a tropical rational function?

Question

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.

Answer 1

Here is an extremely inefficient implementation of Edmonds-Karp (breadth-first search) given as a tropical rational map. (Hopefully I've understood the definition of tropical rational map correctly.)

First, observe that in the usual implementation of Edmonds-Karp, no path is used more than once, since if $p$ is a shortest path with nonzero capacity, the residual edges of $p$ can only be used in a longer path. So if we perform Ford-Fulkerson by iterating over all paths in increasing order of length, the algorithm will terminate with the maximum flow.

Let $\bar{D}$ be the graph obtained by adding, for every edge $a$, a residual edge $\bar{a}$ with target and source reversed. We denote by $\bar{A}$ the set of residual edges. If $a \in \bar{A}$ is a residual edge, we will likewise denote by $\bar{a} \in A$ the edge in the original graph corresponding to $a$. Let $\{p_i\}_{i = 1}^N$ be any fixed enumeration of the acyclic paths from $s$ to $t$ in $\bar{D}$ in increasing order of length.

We will construct our tropical rational map $\mathbb{N}^A \to \mathbb{N}^A$ in three pieces:

First, let $g: \mathbb{N}^A \to \mathbb{N}^{A \sqcup \bar{A}}$ be the augmentation map, taking $c: A \to \mathbb{N}$ to $\bar{c}: A \sqcup \bar{A} \to \mathbb{N}$, where $\bar{c}$ is equal to $c$ on $A$ and identically zero on $\bar{A}$.

For any path $p = (a_1, a_2, \ldots, a_n)$, let $f_p: \mathbb{N}^{A \sqcup \bar{A}} \to \mathbb{N}^{A \sqcup \bar{A}}$ be defined by

$$f_p(c)(a) = \begin{cases} c(a) - \min(c(a_1), \ldots, c(a_n)) \textrm{ if } a \in p,\\ c(a) + \min(c(a_1), \ldots, c(a_n)) \textrm{ if } \bar{a} \in p,\\ c(a) \textrm{ otherwise.}\end{cases}$$

Note that $f_p(c) = c$ if $c$ is zero on any edge in $p$.

Finally, let $r: \mathbb{N}^{A \sqcup \bar{A}} \to \mathbb{N}^A$ be defined by $r(c)(a) = c(\bar{a})$.

Then the composite $r \circ f_{p_N} \circ \cdots \circ f_{p_1} \circ g: \mathbb{N}^A \to \mathbb{N}^A$ is a tropical rational map sending a capacity function $c$ to a maximum-value $c$-flow.

---

EDIT: For completeness, let me give the full argument that if $p$ is a shortest path with nonzero flow, its residual edges can only be used in longer paths. (This is a standard argument in the analysis of the termination and complexity of Edmonds-Karp.)

Denote by $c_i$ the capacity function on $\bar{D}$ after $i$ steps of Edmonds-Karp, and for any vertex $v \in V$, denote by $\ell_i(v)$ the length of the shortest path from $s$ to $v$ in $\bar{D}$ with nonzero $c_i$-flow (i.e., every edge $a$ in the path has $c_i(a) > 0$).

The $(i + 1)$st step of Edmonds-Karp involves flowing along a shortest nonzero-$c_i$-flow path $p$. If $p$ visits vertices $s = v_0, v_1, v_2, \ldots, v_n = t$, then since $p$ is a shortest path, $\ell_i(v_k) = k$ for all $k$. In Edmonds-Karp, we modify the flow capacity by reducing capacity along the edges of $p$ and increasing capacity along the residual edges of $p$. Each residual edge goes from an vertex $v_k$ with $\ell_i(v_k) = k$ to a vertex $v_{k - 1}$ with $\ell_i(v_{k - 1}) = k - 1$.

Now suppose $q$ is a shortest nonzero-$c_{i + 1}$-flow path from $s$ to $t$. Then for each edge from $w_k$ to $w_{k + 1}$ in $q$, $\ell_i(w_{k + 1}) \leq \ell_i(w_k) + 1$, so the length of $q$ is at least $n$ (i.e., the length of $p$), and moreover, if $q$ contains any residual edges of $p$, it must be even longer, since the inequality is strict for those edges. Indeed, by induction, as long as we are flowing along paths of length $n$, we must only be using edges from $w_k$ to $w_{k + 1}$ such that $\ell_i(w_k) = k$ and $\ell_i(w_{k + 1}) = k + 1$.

What this analysis shows is that if we flow along a path $p$ of length $n$ in Edmonds-Karp, we cannot create shorter paths with nonzero flow. Moreover, any other shortest path of length $n$ will not include any residual edges of $p$, so the order in which we try to flow through paths of length $n$ does not matter.

Answer 2

In the comments I suggested that Hillman-Grassl may be related to a "column insertion" version of RSK. Based on a few examples (larger than $2\times 2$) I checked, I am now less sure that there is a direct connection. However, answering your question four, I think that "inverse Hillman-Grassl correspondence", as you call it, (i.e., the map from fillings of $\lambda$ with arbitrary nonnegative integers to reverse plane partitions of shape $\lambda$) can be realized as a tropical rational map.

The reason is: I think the description (which you mentioned) of Hillman-Grassl that appears as Theorem 3.3 in the paper "The Hillman-Grassl correspondence and the enumeration of reverse plane partitions " of Gansner (https://www.sciencedirect.com/science/article/pii/0097316581900418) explains exactly how to do this. Namely, I think to compute the quantity $a_k(M_l)$, in the language of that theorem, we can do the following. Let's call a modified A-chain in $M_l$ a sequence of boxes $u_1,u_2,\ldots,u_m$ in the shape of $M_l$ which does not repeat any boxes and such that $u_{i+1}$ is weakly southwest of $u_i$ for all $i=1,\ldots,m-1$. Associate to such a chain the weight which is simply the sum of the $M_l$ entries of the boxes it visits. Then $a_k(M_l)$ should be the maximum over all collections of $k$ disjoint modified A-chains of the sum of the weights of these chains. This fact, together with the Theorem 3.3, explains how to write the entries of the output reverse plane partition entries as tropical rational functions in the input entries.

EDIT:

Darij, in case you are still interested in this question- I believe this recent preprint of Garver, Patrias, and Thomas https://arxiv.org/abs/1812.08345 not only shows that the Hillman-Grassl correspondence is a PL-function, but in fact gives a "toggle" description of the map, akin to the "toggle" description of PL-RSK. In fact, they show that these two maps (Hillman-Grassl and RSK) are essentially built out of the same toggles, but correspond to two different orientations of the Type A Dynkin diagram.

Answer 3

RE Question 1, I'm not convinced that Ford-Fulkerson does not always converge though*, even if allowed instances where edge capacities are allowed to be non-integers. (It may a priori take exponential time to converge--I'd need to check if there are instances that could take that long, but that would still count as converging.) The example you gave in your link "a stupid choice" is incorrect. What you would infact be left with after your augementing path is two paths from $s$ to $t$ that are vertex-disjoint besides at the endpoints, namely $\langle s,v,u,t \rangle$ and $\langle s,x,w,t \rangle$.

Meanwhile, even besides that, when you talk of a "map" you need to be precise with the domain and range. e.g., when you say "map of $c$" does that mean that $c$ is the domain of the map or the range? How are you representing $c$?

*In fact, I am convinced that Ford-Fulkerson does always converge in finite time. Indeed, for all scalars $K$ if you multiply all capacities in the network by $K$, then a maximum flow in the altered problem would translate to an optimum flow in the original network. Let $K$ be a large enough (but finite!) scalar so that capacity$(e) \not =$capacity$(e')$ implies $|K$capacity$(e) -K$capacity$(e')|$ $\geq 2$. Then wouldn't each augmenting path in the blown-up network (where all capacities are multiplied by $K$) allow at least 1 unit of flow, which would imply that Ford-Fulkerson in this blown-up network would terminate with the optimum flow in a finite number of steps--no more than $K\sum_e$capacity$(e)$ augmenting paths at the very worst.