Min s-t cut in a network

algorithmdata structuresgraph-algorithmnetworking

I am trying to simulate a network of wireless sensor nodes in order to research about the robustness of the network. I am faced with the following problem:

I have a network of nodes with some edge capacities. This is equivalent to something like network flow problem in algorithms. There is a source node (which detects certain events) and a sink node (my base station). Now, I want to find the minimum s-t cut in the network so that the size of the source set is minimized. The source set here refers to the set of nodes separated by the min s-t cut that contains the source.

e.g. if the s-t cut, C = {S,T}, then there is a set of edges which can be removed to separate the network into two sets, S and T and the set S contains the source and T contains the sink. The cut is minimum when the sum of capacities of the edges in the cut is minimum among all possible s-t cuts. There can be several such min-cuts. I need to find a min-cut that has least number of elements in the set S

Note that this is not the original problem but I have tried to simplify it in order to express it in terms of algorithms.

Best Answer

I believe that you can solve this problem by finding a minimum cut in a graph with slightly modified constraints. The idea is as follows - since the cost of a cut is equal to the total capacity crossing the cut, we could try modifying the graph by adding in an extra edge from each node in the graph to t that has capacity one. Intuitively, this would mean that every node in the same part of the cut as s would contribute one extra cost to the total cost of the cut, because the edge from that node to t would cross the edge. Of course, this would definitely mess up the actual min-cut because of the extra capacity. To fix this, we apply the following transformation - first, multiply the capacities of the edges by n, where n is the number of nodes in the graph. Then add one to each edge. The intuition here is that by multiplying the edge capacities by n, we've made it so that the cost of the min-cut (ignoring the new edges from each node to t) will be n times the original cost of the cut. When we then add in the extra one-capacity edges from each node to t, the maximum possible contribution these edges can make to the cost of the cut is n - 1 (if every node in the graph except for t is on the same side as s). Thus the cost of the old min-cut was C, the cost of the new min-cut (S, V - S) is nC + |S|, where |S| is the the number of nodes on the same side of the cut as s.

More formally, the construction is as follows. Given a directed, capacitated graph G and a (source, sink) pair (s, t), construct the graph G' by doing the following:

  1. For each edge (u, v) in the graph, multiply its capacity by n.
  2. For each node v in the graph, add a new edge (v, t) with capacity 1.
  3. Compute a min s-t cut in the graph.

I claim that a min s-t cut in the graph G' corresponds to a min s-t cut in graph G with the fewest number of nodes on the same side of the cut as s. The proof is as follows. Let (S, V - S) be a min s-t cut in G'. First, we need to show that (S, V - S) is a min s-t cut in G. This proof is by contradiction; assume for the sake of contradiction that there is an s-t cut (S', V - S') whose cost is lower than the cost of (S, V - S). Let the cost of (S', V - S') in G be C' and let the cost of (S, V - S) in G be C. Now, let's consider the cost of these two cuts in G'. By constriction, the cost of C' would be nC' + |S'| (since each node on the S' side of the cut contributes one capacity across the cut) and the cost of C would be nC + |S|. Since we know that C' < C, we must have that C' + 1 ≤ C. Thus

nC + |S| ≥ n(C' + 1) + |S| = nC' + n + |S|

Now, note that 0 ≤ |S| < n and 0 ≤ |S'| < n, because there can be at most n nodes on the same side of the cut as s. Thus means that

nC + |S| ≥ nC' + n + |S| > nC' + |S'| + |S| > nC' + |S'|

But this means that the cost of (S, V - S) in G' is greater than the cost of (S', V - S') in G', contradicting the fact that (S, V - S) is a min s-t cut in G'. This allows us to conclude that any min s-t cut in G' is also a min s-t cut in G.

Now, we need to show that not only is a min s-t cut in G' also a min s-t cut in G, but it corresponds to a min s-t cut in G with the fewest number of nodes on the same side of the cut as s. Again, this proof is by contradiction; suppose that (S, V - S) is a min s-t cut in G' but that there is some min s-t cut in G with fewer nodes on the s side of the cut. Call this better cut (S', V - S'). Since (S, V - S) is a min s-t cut in G', it's also a min s-t cut in G, so the cost of (S', V - S') and (S, V - S) in G is some number C. Then the cost of (S, V - S) and (S', V - S') in G' will be nC + |S| and nC + |S'|, respectively. We know that nC + |S'| < nC + |S|, since we've chosen (S', V - S') to be an s-t min cut in G with the fewest number of nodes on the same side as S. But this means that (S', V - S') has a lower cost than (S, V - S), contradicting the fact that (S, V - S) is a min s-t cut in G'. Thus our assumption was wrong and (S, V - S) is a min s-t cut in G with the fewest number of nodes on the same side as S. This completes the correctness proof of the construction.

Hope this helps!

Related Topic