1
$\begingroup$

Here is an exercise I came across while studying MaxFlow / MinCut and I'm rather stumped:

Designate $G = (V, E)$ as an undirected graph that has at least two vertices. Every edge $(e)$ on this graph has capacity $c_e$. Pick two arbitrary vertices from $G$ and label them $s$ and $t$ respectively.

Now, we'll let $P*$ be the set of $s-t$ paths in the graph, and let $C*$ be the set of $s-t$ cuts -- meaning, $C*$ refers to the subset of edges in $G$ that constitute all possible $s-t$ cuts.

Demonstrate that the following equality is true:

$\max_{P\in P*} \min_{e \in P}c_e = \min_{C \in C*}\max_{e \in C}c_e$

My issue: I'm having trouble parsing the above equation. The LHS appears to be describing the longest(?) of all possible s-t paths, and the edge with the minimum capacity along that path. The RHS appears to be describing the minimum number of edges(?) possible in a subset of edges constituting an s-t cut, and the edge with the max. capacity within that subset? I'm frankly not even sure whether the above equation is meant to involve a multiplication.

Still, I figure there must be a way to parse and understand the equation correctly such that the equality would always hold, and that it can be demonstrated as such. I'd appreciate any help in this matter.

$\endgroup$
  • $\begingroup$ At heart, this is not a question about network flows but about understanding mathematical notation. One may argue it should therefore be migrated to Mathematics, but I think the connection to CS is apparent. $\endgroup$ – Raphael Mar 30 '16 at 20:56
2
$\begingroup$

I'm frankly not even sure whether the above equation is meant to involve a multiplication.

No, not at all. We have nesting here:

$\max_{X \in \mathcal{X}}\ ( \min_{x \in X} x)$

is the largest minimum of all $X$. Similarly -- but the other way around -- for $\min \max$. This is very similar to nested quantifiers $\forall$ and $\exists$.

Let, for instance, $\mathcal{X} = \{ \{1,2\}, \{3,4\} \}$. Then, the following equalities hold:

  1. $\min_{X \in \mathcal{X}} \min_{x \in X} x = 1$.
  2. $\min_{X \in \mathcal{X}} \max_{x \in X} x = 2$.
  3. $\max_{X \in \mathcal{X}} \min_{x \in X} x = 3$.
  4. $\max_{X \in \mathcal{X}} \max_{x \in X} x = 4$.

Play around with the example by adding more sets to $\mathcal{X}$, more values to the individual sets, and quantify over $f(x)$ instead of just $x$ for different $f$, in order to get a feeling for this.

If you are inclined to algorithmic thinking, do a quick implementation; you'll see how these operators nest more clearly with types, and examples are faster to compute. For instance, the second example would be

Xs.map { X => X.max }.min
$\endgroup$

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.