title: Karger's Algorithm - Running Time - Edge Contraction
body: <p>In <a href="https://en.wikipedia.org/wiki/Karger%27s_algorithm" rel="nofollow noreferrer">Karger's Min-Cut Algorithm</a> for undirected (possibly weighted) multigraphs, the main operation is to contract a randomly chosen edge and merge it's incident vertices into one metavertex. This process is repeated until two vertices remain. These vertices correspond to a cut. The algo can be implemented with an adjacency list. </p>
  
  <p>Questions: </p>
  
  <ol>
  <li><p>how can I find the particular edge, that has been chosen to be contracted?</p></li>
  <li><p>how does an edge get contracted (in an unweighted and/or weighted graph)?</p></li>
  <li><p>Why does this procedure take quadratic time? </p></li>
  </ol>
  
  <p>Edit: I have found some information that the runtime can be quadratic, due to the fact that we have O(n-2) contractions of vertices and each contraction can take O(n) time. It would be great if somebody could explain me, why a contraction takes linear time in an adjacency list. Note a contraction consists of: deleting one adjacent edge, merging the two vertices into a supernode, and making sure that the remaining adjacent edges are connected to the supernode.</p>
  
  <p>Pseudocode: </p>
  
  <pre><code>procedure contract(G=(V,E)):
  while |V|&gt;2
      choose edge uniformly at random
      contract its endpoints
      delete self loops
  return cut
  </code></pre>
  
  <p>I have read the related topic <a href="https://stackoverflow.com/questions/33486632/karger-min-cut-algorithm-running-time">Karger Min cut algorithm running time</a>, but it did not help me. Also I do not have so much experience, so a "laymens" term explanation would be very much appreciated!</p>