A cut of a graph is a partitioning of the nodes into two nonempty sets.
A minimum cut is a cut that minimizes the number of edges between the sets (i.e. edges where the nodes are in different sets). These edges are called crossing edges.
A graph with \(n\) nodes has \(2^{n-1}-1\) cuts. To see this, just use the binary representation. Let the two sets be \(A\) and \(B\). Let a node be 0 if it ends up in \(A\) - otherwise it is 1. This is just an \(n\) bit binary number. There are \(2^{n}\) such numbers. However, we have to disallow 2 numbers: All 0’s and all 1’s as the sets need to be nonempty. Further, we should divide the result by 2, as we can swap \(A\) and \(B\) (i.e. 0011 is the same cut as 1100).
Applications
- Identify communities in social networks.
- Identify network weaknesses.
- Identify objects in an image
Karger’s Algorithm
The algorithm is almost trivial:
While there are more than 2 vertices:
- Pick an edge at random.
- “Contract” the nodes on that edge into one “super” node. If there are any self loops, remove them.
Once you’re left with two “nodes”, those two nodes represent the partitioning.
This algorithm gives no guarantees on being minimal. So rerun it \(N\) times and pick the smallest one you get.
Analysis
This algorithm gives no guarantees on being minimal.
Say we want to get a given minimal cut \((A,B)\). Suppose we have \(n\) nodes and \(m\) edges. let \(k\) be the number of crossing edges in the minimal cut. Call these edges \(F\).
Now take an edge in \(F\). In the algorithm, it’ll either be contracted or not. If it is contracted, then we can not get \((A,B)\).
If no edges in \(F\) are contracted, we get the desired minimal cut.
Let \(S_{i}\) be the event that an edge in \(F\) is contracted in step \(i\). We need to compute:
\(P(S_{1})=\frac{k}{m}\) Also, note that the degree of each vertex is at least \(k\) by construction. If it weren’t, we could get a cut with \(A\) being that node and \(B\) being all other nodes. Another invariant is that the sum of the degrees of all nodes is \(2m\) (for all graphs). Putting the two together, we get \(2m\ge kn\). This gives us \(P(S_{1})\le\frac{2}{n}\). This is a useful result as we don’t need to know \(k\).
Now \(P\left(S_{1}'\bigcap S_{2}'\right)=P(S_{2}'|S_{1}')P(S_{1}')\). The first term on the RHS is \(1-\) \(k\) over the remaining edges. Using the fact that the degrees in the contracted graph are at least \(k\), we get the number of remaining edges be at least \(\frac{1}{2}k(n-1)\).
This gives \(P(S_{2}'|S_{1}')\ge1-\frac{2}{n-1}\)
If we take this out to \(n-2\) steps, we get:
Multiplying out gives us \(P\ge\frac{2}{n(n-1)}\ge\frac{1}{n^{2}}\)
This is not very auspicious. \(n\) can be large! It’s still a lot better than picking a random cut, as there are \(2^{n-1}-1\) of them.
We may repeat the algorithm many times. In particular, if we repeat this \(n^{2}\ln n\) times, the probability we don’t get this cut is less than \(1/n\), which is pretty good (using the \(1+x\le e^{x}\) inequality).
The run time is \(\Omega(Nm)\) where \(N\) is the number of times you run the algorithm.
Faster algorithms do exist!
Keep in mind that this analysis assumes a given cut. There could be many minimal cuts.
Upper Bound on Number of Minimal Cuts
We know that the probability of getting a given minimal cut using the contraction algorithm is at least \(\frac{1}{\dbinom{n}{2}}\) from above. As the cuts are independent, we can simply sum the probabilities of getting each cut using the algorithm. As the sum is bounded by 1, the number of minimal cuts cannot exceed \(\dbinom{n}{2}\).
This establishes an upper bound. Is it tight? Yes. Consider a graph that is simply a ring/cycle. All cuts are minimal with \(k=2\). You can get a cut by picking any 2 edges. There are \(m=n\) edges, so you have \(\dbinom{m}{2}\) unique minimal cuts. This is an example of a graph that reaches the upper bound.
Implementations
Python
Use the nx.minimum_edge_cut function in NetworkX