Let $N$ be a flow network with nodes $V$ and edges $E$. For technical reasons, the source side of a minimum $s$-$t$ cut $(A,B)$ with $s \in A$ and $t \in B$ is defined as $A - \{s\}$. Now, let $\mathcal{R}(N)$ be the set of the source sides of all minimum $s$-$t$ cuts of $N$. $\mathcal{R}(N)$ is now a non-empty family of sets over the universe $E$. Due to submodularity, the intersection of two source sides and the union of two source sides yields the source side of a min-cut. As such, $\mathcal{R}(N)$ is a ring. Hence, for every network $N$, $\mathcal{R}(N)$ is a finite ring of sets.

By ring of sets, I refer to the definition of a non-empty family of sets closed under union and intersection. Hence, a ring of sets is commutative.

I wonder if the converse direction is true, that is if the following statement holds:

For every ring of sets $\mathcal{R}$ over a finite universe $U$ there is a flow network $N$ with nodes $U$ such that $\mathcal{R}(N) = \mathcal{R}$.

I was unable to come up with a counter example, at the same time literature seems not to know this either. To me it seemed like a constructive proof could work where the family of sets is analyzed in order to determine whether the nodes of $U$ need to be parallel or in series.

  • 1
    $\begingroup$ I assume you mean "For every finite commutative ring...". $\endgroup$
    – Jeffε
    Sep 29 '14 at 2:18
  • $\begingroup$ Good point, the universe has to be finite, of course. Moreover, I didn't really mean a ring in its generality, but a ring of sets which is commutative by definition. I edited the question accordingly. $\endgroup$ Sep 29 '14 at 6:52
  • $\begingroup$ If $V=U\cup\{s,t\}$, i.e. source and sink can be outside $U$, then the answer is positive. $\endgroup$ Sep 29 '14 at 9:38

Here I'll show that the statement is true, assuming that $V=U\cup\{s,t\}$, i.e. source and sink are not elements of $U$.

Let $S=\bigcap\limits_{R\in\mathcal R}R$, $P=\bigcup\limits_{R\in\mathcal R}R\setminus S$ and $T=U\setminus(S\cup P)$. Construct a flow network $N$ with nodes $U\cup\{s,t\}$ and the following edges:

  • From $s$ to every element of $S$.
  • From every element of $T$ to $t$.
  • For all ordered pairs $(x,y)$ such that $x\in P$, $y\in P$ and $\forall R\in\mathcal R:x\in R\rightarrow y\in R$, from $x$ to $y$.

Each edge can have any positive capacity. Since $t$ is not reachable from $s$, maximal flow is $0$.

What remains is to prove that the set of source sides of minimal $s$-$t$ cuts is exactly $\mathcal R$. Firstly, I'll show that any set $R\in\mathcal R$ is a source side of an $s$-$t$ cut. By definition, $S\subset R$ and $T\cap R=\emptyset$, so edges from $s$ and edges to $t$ don't cross the cut. Edges in $P$ also don't cross the cut by definition, since for any such edge $x\rightarrow y$, if $x$ is in $R$, $y$ must be in $R$ as well.

Now I'll show that if $Q$ is a source side of a minimal $s$-$t$ cut, $Q$ must be in $\mathcal R$. Since maximal flow is zero, there must be no edges crossing the cut. Therefore, $S\subset Q$ and $T\cap Q=\emptyset$. If $Q=S$, the proof is done, because $S$ is a member of $\mathcal R$ by definition. Otherwise, let $Q'=\bigcup\limits_{x\in Q}\bigcap\limits_{R\in\mathcal R\wedge x\in R}R$. By definition, $Q'\in\mathcal R$, so it remains to show that $Q=Q'$.

Note that every intersection in the definition of $Q'$ is nonempty, because $Q\subset S\cup P$. Also, $Q'\subset S\cup P$. By definition, every element of $Q$ is contained in $Q'$. Suppose that there is an element $y\in Q'$ which is not in $Q$. Then $y\in P$ and there is an element $x\in Q$ such than $\forall R\in\mathcal R:x\in R\rightarrow y\in R$. Then $x\in P$, since otherwise $x\in S$ and $S\in\mathcal R$ is a counterexample. So, there must be an edge from $x$ to $y$, and it crosses the cut, a contradiction. Therefore, $Q=Q'$, so $Q\in\mathcal R$.

By the way, while the above solution requires directed edges, the answer is the same even if all the edges must be undirected (with the same capacity in both directions). The idea for the solution in this case is that you need such a network that, after the maximal flow is pushed through it, the residual graph is the same as the graph constructed using the solution above plus some edges from $T$ to $P$ and from $P$ to $S$ which don't change the set of minimal cuts. The details are left as an exercise to the reader.


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.