Karger's algorithm

<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a> and <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, Karger's algorithm is a <a href="/facts/Randomized_algorithm/Fngl1zgk">randomized algorithm</a> to compute a <a href="/facts/Minimum_cut/xWTNp1hN">minimum cut</a> of a connected <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a>. It was invented by <a href="/facts/David_Karger/mr17YBKD">David Karger</a> and first published in 1993.
</p><p>The idea of the algorithm is based on the concept of <a href="/facts/Edge_contraction/PRqKXEkj">contraction of an edge</a> 
  
    
      
        (
        u
        ,
        v
        )
      
    
    {\displaystyle (u,v)}
  
 in an undirected graph 
  
    
      
        G
        =
        (
        V
        ,
        E
        )
      
    
    {\displaystyle G=(V,E)}
  
. Informally speaking, the contraction of an edge merges the nodes 
  
    
      
        u
      
    
    {\displaystyle u}
  
 and 
  
    
      
        v
      
    
    {\displaystyle v}
  
 into one, reducing the total number of nodes of the graph by one. All other edges connecting either 
  
    
      
        u
      
    
    {\displaystyle u}
  
 or 
  
    
      
        v
      
    
    {\displaystyle v}
  
 are "reattached" to the merged node, effectively producing a <a href="/facts/Multigraph/udmS0Cp0">multigraph</a>. Karger's basic algorithm iteratively contracts randomly chosen edges until only two nodes remain; those nodes represent a <a href="/facts/Cut_(graph_theory)/1lKf2IIW">cut</a> in the original graph. By iterating this basic algorithm a sufficient number of times, a minimum cut can be found <a href="/facts/With_high_probability/eBttFkd4">with high probability</a>.
</p>

Karger's algorithm open-in-new

Karger's algorithm