Suppose I have a directed s-t graph with edge capacities.
I know how to compute a min-cut (using max-flow min-cut ) of this graph.
What I would like to know is
1. Is there a method to find all possible min-cuts on this graph?
   Can you explain and list this method?
2. If I already have a min-cut (or a max-flow) and I modify the graph 
   slightly e.g change connections, introduce new nodes and new edges.
   Is there a way to quickly compute the min-cut of this modified graph.

---

Clarification of Question by darkavenger-ga on 13 Dec 2002 12:32 PST

Hi, My question is out of curiosity since both parts seem
to be solvable but I can't find references. It seems intuitively
possible to generate other min-cuts if you have a min-cut
and also to generate a new min-cut if you only modify the graph slightly.

---

Clarification of Question by darkavenger-ga on 13 Dec 2002 12:34 PST

Hi, I also wish to add that I know about all methods to compute one
min-cut on the graph, from Ford-Fulkerson to more advanced methods.

Hi, darkavenger:

Thanks for posting this interesting question about computational graph
theory.  As you probably know, the usual approach to solving a min-cut
problem is by considering it to be the dual of a max-flow problem (on
a directed graph with a single source and single sink).  The topic is
generally related to some others that I have posted on here.

I would be interested in answering this problem, but the price offered
($5) is really appropriate for only a brief answer, perhaps a single
line.

Here is a link to guidelines about pricing your question, 

https://answers.google.com/answers/pricing.html 

Problems with multiple parts such as yours would generally merit a $50
or more list price, although it is always possible that a Researcher
with special interest in a particular subject may attempt an answer
for less.

If you both raise your price and also post a clarification here, the
system will notify me and I will take another look at your question.

regards, mathtalk-ga