24
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Re: your question 2- I think Hillman-Grassl can be described in terms of toggles; moreover, I think it corresponds to "column insertion RSK." I don't know of any written reference for this but I think people in the integrable probability community know about this $\endgroup$ – Sam Hopkins Apr 4 '18 at 23:20
  • $\begingroup$ P.S. I didn't find that "alternative" I just wrote what Alex Postnikov explained; and I think he knew about it from Kirillov et al. $\endgroup$ – Sam Hopkins Apr 4 '18 at 23:21
  • $\begingroup$ It's helpful to think about the smallest nontrivial case, $2\times 2$ matrices. RSK gives $\begin{pmatrix} a & b \\ c & d \end{pmatrix} \to \begin{pmatrix} min(b,c) & a+b \\ a+c & a+max(b,c)+d \end{pmatrix}$. Hillman-Grassl/column RSK gives $\begin{pmatrix} a & b \\ c & d \end{pmatrix} \to \begin{pmatrix} min(a,d) & a+b \\ a+c & b+c+max(a,d) \end{pmatrix}$. I think these are the only two possible tropical functions that satisfy the requisite properties. $\endgroup$ – Sam Hopkins Apr 4 '18 at 23:25
  • $\begingroup$ @SamHopkins: Tom and I have done the $2\times 2$ case in our SageMath project a few days ago, and we have good reasons to believe that it is uncharacteristically simple. For example, take the composition of Hillman-Grassl and "RSK" (Hopkins/Pak/Sulzgruber); this is a permutation of the set of all $\mathbb{N}$-matrices. What is the order of this permutation? In the $2\times 2$-case, it is $2$, as follows easily from the formulas you gave. In the $2\times 3$-case, the order appears to be infinite (though maybe something can be said if the sum of the entries is fixed). $\endgroup$ – darij grinberg Apr 4 '18 at 23:44
  • $\begingroup$ @SamHopkins: I don't know why Hillman-Grassl corresponds to "column RSK", and how it can be built from toggles; literature is vague and lacunar around these questions. $\endgroup$ – darij grinberg Apr 4 '18 at 23:45
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is interesting, but somewhat hard to digest. First, I don't understand your argument for why no path is used more than once in Edmonds-Karp; but I know that it is true (it follows easily from the proof of Theorem 4.4 in Lex Schrijver's A Course in Combinatorial Optimization, because that proof shows that every time we use a shortest path to augment the flow, we lose at least one arc of this path from the residual digraph, and this arc cannot come back until we are out of shortest paths of the given size). $\endgroup$ – darij grinberg Apr 7 '18 at 4:10
  • $\begingroup$ Next, I am a bit unused to working with $\mathbb{N}^{A \sqcup \overline{A}}$, but of course it makes sense: You aren't really using the full set $\mathbb{N}^{A \sqcup \overline{A}}$, but only the subset $Z$ of $\mathbb{N}^{A \sqcup \overline{A}}$ consisting of all maps $h : A \sqcup \overline{A} \to \mathbb{N}$ that have the property that $h\left(a\right) + h\left(\overline{a}\right) = c\left(a\right)$ for each $a \in A$. The original map $\overline{c}$ belongs to this subset $Z$, and the maps $f_p$ all take $Z$ into $Z$, so that the algorithm never "leaves" $Z$. Thus, ... $\endgroup$ – darij grinberg Apr 7 '18 at 4:12
  • $\begingroup$ ... at each step of Edmonds-Karp, after we have used up the paths $p_1, p_2, \ldots, p_k$ for augmentation, the value of our flow at each arc $a \in A$ is $\left( \left(f_{p_k} \circ f_{p_{k-1}} \circ \cdots \circ f_{p_1}\right) \left(\overline{c}\right) \right) \left( \overline{a} \right)$, whereas $\left( \left(f_{p_k} \circ f_{p_{k-1}} \circ \cdots \circ f_{p_1}\right) \left(\overline{c}\right) \right) \left( a \right)$ is the unused capacity on that arc (i.e., it is $c\left(a\right)$ minus that value). $\endgroup$ – darij grinberg Apr 7 '18 at 4:14
  • $\begingroup$ But here is an issue that I cannot resolve: Why must the fixed ordering $\left(p_1, p_2, \ldots, p_N\right)$ of all paths $s \to t$ in $\overline{D}$ match the ordering in which Edmonds-Karp uses up these paths? Sure, both orderings have the property that a shorter path always comes before a longer path; but two paths of the same size may appear in different orders. Are you implicitly saying that it doesn't matter? If so, why not? What if $p_5$ and $p_9$ are two paths of the same length, and, in Edmonds-Karp, I have to use $p_9$ before $p_5$ because $p_5$ doesn't ... $\endgroup$ – darij grinberg Apr 7 '18 at 4:18
  • 1
    $\begingroup$ @darijgrinberg: I've clarified my answer along the lines you've suggested here in the comments. I agree that the dependence on ordering is unavoidable, though of course one can choose an ordering induced by an ordering on the edges as a somewhat-non-arbitrary choice. I'm also not optimistic that a tropical rational function can be made efficient (i.e., able to skip all the zero-flow paths), as that would seem to require a level of control-flow that tropical rational functions are unable to express, but I don't know how to make this intuition precise. $\endgroup$ – Evan Jenkins Apr 8 '18 at 16:52
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Here’s maybe another way to think about it: put a partial order on the boxes of $lambda$ whereby $u\leq u’$ if $u$ is weakly southwest of $u’$ (an unusual order). Then to get $a_k(M_l)$ we take the maximum over subposets of the shape of $M_l$ with maximum antichain size less than or equal to $k$ of the sum of the entries of the boxes in this subposet. $\endgroup$ – Sam Hopkins Apr 12 '18 at 19:45
  • $\begingroup$ It's not that I've lost interest, but the amount of reading up that understanding the Garver/Patrias/Thomas work seems to require is heavily daunting. (I admit having wondered myself about possible interpolations between PL-RSK and Hillman-Grassl myself, particularly as I've seen Sulzgruber's Hillman-Grassl-like redefinition of the former.) $\endgroup$ – darij grinberg Jan 21 at 20:28
  • $\begingroup$ @darijgrinberg: Vic suggested this paper for a seminar/reading group this semester :) $\endgroup$ – Sam Hopkins Jan 21 at 20:30
  • $\begingroup$ Count me interested (hopefully not on MWF < 13:00). $\endgroup$ – darij grinberg Jan 21 at 20:32
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have clarified (I believe) the "map". $\endgroup$ – darij grinberg Apr 4 '18 at 23:52
  • 1
    $\begingroup$ Is this example en.wikipedia.org/wiki/… wrong too? $\endgroup$ – darij grinberg Apr 4 '18 at 23:53
  • $\begingroup$ Hi Darij, the counterexample via this link looks nice and correct (will give it a third look to make sure), so it looks like there is an error in my post--it looks the lower bound on the value of difference between different capacities does not imply a lower bound on the improvement of each update. $\endgroup$ – Mike Apr 5 '18 at 1:57
  • $\begingroup$ I can't follow the "$\geq 2$" argument (assuming you want your up-scaled capacities to be floored so they become integers), so yeah, I suspect some mistake in the handwaving. $\endgroup$ – darij grinberg Apr 5 '18 at 2:00
  • $\begingroup$ Well I put in the \ge 2 "just to make sure". But yes indeed, regardless there was a logical flaw in my handwaving, the counterexample you posted establishs that. It really goes to show that a proof is not truly a proof until the last i is dotted and the last t is crossed! $\endgroup$ – Mike Apr 5 '18 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.