User:Venkat badri/sandbox

This is the user sandbox of Venkat badri. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here. Other sandboxes: Main sandbox | Template sandbox Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

Randomized algorithm for minimum cuts

A graph and two of its cuts. The dotted line in red is a cut with three crossing edges. The dashed line in green is a min-cut of this graph, crossing only two edges.

In computer science and graph theory, Karger's algorithm is a randomized algorithm to compute a minimum cut of a connected graph. It was invented by David Karger and first published in 1993.^[1]

The idea of the algorithm is based on the concept of contraction of an edge ${\displaystyle (u,v)}$ in an undirected graph ${\displaystyle G=(V,E)}$. Informally speaking, the contraction of an edge merges the nodes ${\displaystyle u}$ and ${\displaystyle v}$ into one, reducing the total number of nodes of the graph by one. All other edges connecting either ${\displaystyle u}$ or ${\displaystyle v}$ are "reattached" to the merged node, effectively producing a multigraph. Karger's basic algorithm iteratively contracts randomly chosen edges until only two nodes remain; those nodes represent a cut in the original graph. By iterating this basic algorithm a sufficient number of times, a minimum cut can be found with high probability.

The global minimum cut problem

Main article: Minimum cut

A cut ${\displaystyle (S,T)}$  in an undirected graph ${\displaystyle G=(V,E)}$  is a partition of the vertices ${\displaystyle V}$  into two non-empty, disjoint sets ${\displaystyle S\cup T=V}$ . The cutset of a cut consists of the edges ${\displaystyle \{\,uv\in E\colon u\in S,v\in T\,\}}$  between the two parts. The size (or weight) of a cut in an unweighted graph is the cardinality of the cutset, i.e., the number of edges between the two parts,

${\displaystyle w(S,T)=|\{\,uv\in E\colon u\in S,v\in T\,\}|\,.}$ 

There are ${\displaystyle 2^{|V|}}$  ways of choosing for each vertex whether it belongs to ${\displaystyle S}$  or to ${\displaystyle T}$ , but two of these choices make ${\displaystyle S}$  or ${\displaystyle T}$  empty and do not give rise to cuts. Among the remaining choices, swapping the roles of ${\displaystyle S}$  and ${\displaystyle T}$  does not change the cut, so each cut is counted twice; therefore, there are ${\displaystyle 2^{|V|-1}-1}$  distinct cuts. The minimum cut problem is to find a cut of smallest size among these cuts.

For weighted graphs with positive edge weights ${\displaystyle w\colon E\rightarrow \mathbf {R} ^{+}}$  the weight of the cut is the sum of the weights of edges between vertices in each part

${\displaystyle w(S,T)=\sum _{uv\in E\colon u\in S,v\in T}w(uv)\,,}$ 

which agrees with the unweighted definition for ${\displaystyle w=1}$ .

A cut is sometimes called a “global cut” to distinguish it from an “${\displaystyle s}$ -${\displaystyle t}$  cut” for a given pair of vertices, which has the additional requirement that ${\displaystyle s\in S}$  and ${\displaystyle t\in T}$ . Every global cut is an ${\displaystyle s}$ -${\displaystyle t}$  cut for some ${\displaystyle s,t\in V}$ . Thus, the minimum cut problem can be solved in polynomial time by iterating over all choices of ${\displaystyle s,t\in V}$  and solving the resulting minimum ${\displaystyle s}$ -${\displaystyle t}$  cut problem using the max-flow min-cut theorem and a polynomial time algorithm for maximum flow, such as the push-relabel algorithm, though this approach is not optimal. Better deterministic algorithms for the global minimum cut problem include the Stoer–Wagner algorithm, which has a running time of ${\displaystyle O(mn+n^{2}\log n)}$ .^[2]

Contraction algorithm

The fundamental operation of Karger’s algorithm is a form of edge contraction. In the edge contraction process, we randomly select an edge ${\displaystyle e=\{u,v\}}$  from the graph. We then merge the two nodes ${\displaystyle u}$  and ${\displaystyle v}$  into a single node, and reattach any edges that were connected to either ${\displaystyle u}$  or ${\displaystyle v}$  to the newly merged node. Self-loops (edges from a node to itself) are removed during this process. This contraction reduces the number of nodes in the graph by one, and we repeat this process until only two nodes remain, which defines the final cut in the graph.

 

The contraction algorithm repeatedly contracts random edges in the graph, until only two nodes remain, at which point there is only a single cut.

The key idea of the algorithm is that it is far more likely for non min-cut edges than min-cut edges to be randomly selected and lost to contraction, since min-cut edges are usually vastly outnumbered by non min-cut edges. Subsequently, it is plausible that the min-cut edges will survive all the edge contraction, and the algorithm will correctly identify the min-cut edge.

 

Successful run of Karger’s algorithm on a 10-vertex graph. The minimum cut has size 3.

   procedure contract(${\displaystyle G=(V,E)}$ ):
   while ${\displaystyle |V|>2}$ 
       choose ${\displaystyle e\in E}$  uniformly at random
       ${\displaystyle G\leftarrow G/e}$ 
   return the only cut in ${\displaystyle G}$ 

When the graph is represented using adjacency lists or an adjacency matrix, a single edge contraction operation can be implemented with a linear number of updates to the data structure, for a total running time of ${\displaystyle O(|V|^{2})}$ . Alternatively, the procedure can be viewed as an execution of Kruskal’s algorithm for constructing the minimum spanning tree in a graph where the edges have weights ${\displaystyle w(e_{i})=\pi (i)}$  according to a random permutation ${\displaystyle \pi }$ . Removing the heaviest edge of this tree results in two components that describe a cut. In this way, the contraction procedure can be implemented like Kruskal’s algorithm in time ${\displaystyle O(|E|\log |E|)}$ .

 

The random edge choices in Karger’s algorithm correspond to an execution of Kruskal’s algorithm on a graph with random edge ranks until only two components remain.

The best known implementations use ${\displaystyle O(|E|)}$  time and space, or ${\displaystyle O(|E|\log |E|)}$  time and ${\displaystyle O(|V|)}$  space, respectively.^[1]

Success probability of the contraction algorithm

In a graph ${\displaystyle G=(V,E)}$  with ${\displaystyle n=|V|}$  vertices, the contraction algorithm returns a minimum cut with polynomially small probability ${\displaystyle {\binom {n}{2}}^{-1}}$ . Recall that every graph has ${\displaystyle 2^{n-1}-1}$  cuts (by the discussion in the previous section), among which at most ${\displaystyle {\tbinom {n}{2}}}$  can be minimum cuts. Therefore, the success probability for this algorithm is much better than the probability for picking a cut at random, which is at most ${\displaystyle {\frac {\tbinom {n}{2}}{2^{n-1}-1}}}$ .

For instance, the cycle graph on ${\displaystyle n}$  vertices has exactly ${\displaystyle {\binom {n}{2}}}$  possible cuts, all of which are minimum cuts. The probability of returning the minimum cut by randomly selecting an edge and contracting it is ${\displaystyle 2n{\binom {n}{2}}^{-1}={\frac {2}{n}}}$ . This probability increases with every repetition of the algorithm. After repeating the algorithm ${\displaystyle O(n^{2}\log n)}$  times, the probability of finding the minimum cut approaches 1.

Improvements

The time complexity of the algorithm can be improved by using parallelism or optimization techniques. A parallel implementation, for instance, can perform edge contractions simultaneously on multiple parts of the graph, which may significantly reduce the overall runtime.

Category:Graph algorithms Category:Randomized algorithms Category:Computational geometry Category:1993 introductions

1. Karger, David (1993). "Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm". Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms.
2. Stoer, M.; Wagner, F. (1997). "A simple min-cut algorithm". Journal of the ACM. 44 (4): 585. doi:10.1145/263867.263872. S2CID 15220291.