-1

I want to implement the min cut algorithm form Karger.

Wikipedia claims it is possible to write an implementation with a running time of O(|V|^2). I don't see any way to do this. The algorithm makes |V| iterations and in each iteration it contracts an edge. To contract an edge you need to:

  1. create a new vertex,
  2. delete the two old vertexes and
  3. delete the edges between the old vertexes.

There is no data structure for graphs which can add vertexes, delete vertexes and delete edges in O(|V|). Wikipedia recommends an adjacency lists but it has an running time of O(|V|+|E|) which is bad if you have |E|=|V|^2. Is it possible to implement the Karger's min cut in O(|V|^2)?

Yu Zhang
  • 2,037
  • 6
  • 28
  • 42
Asker
  • 431
  • 5
  • 14
  • The CS stack exchange discussing is using a adjacency list and it is only about how to contract not how fast it is. – Asker Nov 02 '15 at 21:37
  • The edge contraction takes O(V^2) time, not the entire algorithm. – chepner Nov 02 '15 at 22:14
  • Ok but our professor said that the whole algorithm is possible in O(|V|^2). Is that true? Maybe use a hash table to store the graph. – Asker Nov 02 '15 at 22:18

1 Answers1

0

Wikipedia left out the detail that you need an adjacency list with weighted edges, so that you can merge parallel edges by adding their weights. In this way, the (unweighted) degree is bounded by |V| at each step.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • How does it matter if the edges are weighted ? The problem is that vertex deletion allways is O(|E|) and |E| can be |V|^2 or? – Asker Nov 02 '15 at 23:02
  • 1
    @Asker You need to merge parallel edges. Then vertex deletion is O(|V|). – David Eisenstat Nov 02 '15 at 23:09
  • How do I merge parallel edges in O(|V|^2)? I think you need to check each edge if it is a parallel edge but it is possible to have more than |V|^2 edges. Thank you for your response. – Asker Nov 03 '15 at 13:19
  • @Asker Bucket sorting. Only the edges that were incident to one of the endpoints of the contracted edge need to be examined at each step. – David Eisenstat Nov 03 '15 at 14:08