## algorithms – Finding s-t min-cut of undirected graph

Given an undirected graph with non-negative edge weights, and two vertices $$s,t$$ in the graph. I would like to find the minimal cut such that $$s$$ and $$t$$ are on different sides of the cut.

For example I have a graph describing the network of roads connecting Berlin and Munich and I want to find the minimal cut such that Berlin and Munich fall on different sides of the cut.

I know of an algorithm for global minimal cut (Karger), which wouldn’t guarantee that $$s$$ and $$t$$ are not on the same side of the cut. The best thing I managed to find was this article for finding the s-t min-cut of a directed graph (flow network).

I think I can use the flow network algorithm to solve the problem by doing the following:

1. Make my undirected graph directed by replacing each edge with two directed edges.
2. Apply the “minimum s-t cut in a flow network” algorithm on step one’s graph to find all edges of the directed s-t min-cut.
3. For the undirected case the s-t min-cut consists off all edges where at least of its directed was in step two’s min-cut.

Is there a more efficient algorithm for this problem specifically for undirected graphs?

Thanks!

## How to prove that the dual linear program of the max-flow linear program indeed is a min-cut linear program?

So the wikipedia page gives the following linear programs for max-flow, and the dual program :

While it is quite straight forward to see that the max-flow linear program indeed computes a maximum flow (every feasable solution is a flow, and every flow is a feasable solution), i couldn’t find convincing proof that the dual of the max-flow linear program indeed is the LP of the min-cut problem.

An ‘intuitive’ proof is given on wikipedia, namely : $$d_{uv}$$ is 1 if the edge $$(u,v)$$ is counted in the cut and else $$0$$, $$z_u$$ is $$1$$ if $$u$$ is in the same side than $$s$$ in the cut, and $$0$$ if $$u$$ is in the same side of the cut than $$t$$

But that doesn’t convince me a lot, mainly why should all the variables be integers, while we don’t have integer conditions ?

And in general, do you have a convincing proof that the dual of the max-flow LP indeed is the LP formulation for min-cut ?

Edit : Ok i found a proof here http://theory.stanford.edu/~trevisan/cs261/lecture15.pdf , however it only gives a probabilistic way to build the cut from the variables assignement of the LP.

## graphs – Check if a pair of vertices belongs to the min-cut

Given a digraph $$G = (V, A)$$ with a source $$s in V$$ and a sink $$t in V$$, I need to adapt the graph to find out if a pair of vertices $$u in V$$ and $$v in V$$ belongs to the min-cut $$S$$ Between $$s$$ and $$t$$. In other words, a new summit $$a$$ belongs to the min-cut $$S$$ if and only if $$u in S$$ and $$v in S$$. This new vertex must maintain the original max flow of $$s$$ at $$t$$. I tried to create new arcs $$(u, a)$$ and $$(a, v)$$ with endless abilities, but while $$a$$ belongs to $$S$$ when $$u in S$$, it forces immediately $$v$$ To belong to $$S$$ also, which is not necessarily true if the maximum flow was calculated in the original graph $$G$$. So is there a way to force a new node to be in the min-cut set $$S$$ if a pair of vertices belongs to $$S$$?

## ford fulkerson – Min-cut in a zero flow network from source to well

The max-cut min-flow theorem ensures that the minimum cut of a directed network is equal to the maximum throughput. And we can calculate $$S$$ and $$T$$, are disjoint subsets containing the source and receiver nodes of the residual graph, respectively.

What will be $$S$$ and $$T$$ if the maximum flow from the source to the well is equal to 0, there is no path led from $$s$$ at $$t$$? is $$S$$ is going to be the singleton set {s} or its empty set $$phi$$ and $$T$$ to be the set of summits $$V$$?

## In a Min-Cut problem, how often do I have to run Karger's algorithm in a given set of nodes?

Question:

On 22 nodes, how many times do I have to run Karger's algorithm to find a min-cut problem in an error range (for example, <2 or between 0 and 1)?

## Confusion about Min-Cut probabilities

• Watching a video on Counting Minimum Cuts by Tim Roughgarden.
• $$(A_ {i}, B_ {i}) = big ((A_ {1}, B_ {1}), …, (A_ {t}, B_ {t}) big) forall i in Bbb {R}$$
• $$P big ((A_ {i}, B_ {i}) big) geq frac {1} { begin {pmatrix} n \ 2 end {pmatrix}} = p$$, which I interpret as the lower limit of the probability of having at least a minimal reduction.
• In the following problem, two answers A and B are highlighted as correct. I understand why A is correct but I am puzzled why B is also marked as correct.
• A: for each graph $$G$$ with $$n$$ knots and every min cut $$(A, B)$$ (I'm assuming the same thing as $$(A_ {i}, B_ {i})$$) $$P big ((A, B) big) geq p$$.
• B There is a graph $$G$$ with $$n$$ knots and a min cut $$(A, B)$$ (still assuming the same thing as $$(A_ {i}, B_ {i})$$) of $$G$$ such as $$P big ((A, B) big) leq p$$.