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.

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

Your Answer

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

Browse other questions tagged or ask your own question.