# Characterization of the Set of all s-t-Min-Cut Edge Sets

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.

• Just to clarify, you are looking for a characterization of those S where the answer is yes, right? Apr 22 '15 at 20:38
• Yes. Alternatively, I would like to know the complexity of the problem stated above. Apr 22 '15 at 20:40
• 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 Apr 24 '15 at 10:58