<p>I would like to know how to answer the following problem:</p>
<blockquote>
<p>Input: A family of sets <span class="math-container">$S$</span> over a universe <span class="math-container">$U$</span>.</p>
<p>Question: Is there a directed flow network <span class="math-container">$N$</span> with edges <span class="math-container">$U$</span> such that the set of all <span class="math-container">$s$</span>-<span class="math-container">$t$</span> min-cut edge sets is exactly <span class="math-container">$S$</span>?</p>
</blockquote>
<p>A min-cut edge set is the set of edges crossing a min-cut in <span class="math-container">$s$</span>-<span class="math-container">$t$</span> direction.</p>
<p>I have come up with a partial solution: If there are three sets <span class="math-container">$A,B,C \in S$</span> such that the symmetric difference of <span class="math-container">$A$</span> and <span class="math-container">$B$</span> is a subset of <span class="math-container">$C$</span>, then the answer to the problem is no. Unfortunately, this does not suffice.</p>

CC BY-SA 3.0
2015-04-22T20:38:03.097Z
Just to clarify, you are looking for a characterization of those S where the answer is yes, right?
Kaveh
CC BY-SA 3.0
2015-04-22T20:40:01.623Z
Yes. Alternatively, I would like to know the complexity of the problem stated above.
Oliver Witt
CC BY-SA 3.0
2015-04-24T10:58:49.353Z
You may want to have a look at this paper: J-C Picard, M Queyranne. On the structure of all minimum cuts in a network and applications, Mathematical Programming Study 13 (1980), 8-16. They show that a set A of \emph{vertices} is the set of vertices on the side of a minimum cut that contains s iff A is the reachability set in G′ of some subset that contains s but not t, where G′ is the residual network after a max-flow computation in N
david
<graph-theory><max-flow-min-cut><flow-problems>
Characterization of the Set of all s-t-Min-Cut Edge Sets
Oliver Witt
# Characterization of the Set of all s-t-Min-Cut Edge Sets

(Asked by: username_0 on 2014-11-21)

I would like to know how to answer the following problem:

> Input: A family of sets $S$ over a universe $U$.
>
> Question: Is there a directed flow network $N$ with edges $U$ such that the set of all $s$-$t$ min-cut edge sets is exactly $S$?

A min-cut edge set is the set of edges crossing a min-cut in $s$-$t$ direction.

I have come up with a partial solution: If there are three sets $A,B,C \in S$ such that the symmetric difference of $A$ and $B$ is a subset of $C$, then the answer to the problem is no. Unfortunately, this does not suffice.

**Tags:** graph-theory, max-flow-min-cut, flow-problems
> **Comments:**
> **username_1**: Just to clarify, you are looking for a characterization of those S where the answer is yes, right?  
> **username_0**: Yes. Alternatively, I would like to know the complexity of the problem stated above.  
> **username_2**: You may want to have a look at this paper: J-C Picard, M Queyranne. On the structure of all minimum cuts in a network and applications, Mathematical Programming Study 13 (1980), 8-16. They show that a set A of \emph{vertices} is the set of vertices on the side of a minimum cut that contains s iff A is the reachability set in G′ of some subset that contains s but not t, where G′ is the residual network after a max-flow computation in N  

---

## 0 answers

