Coffee + graphs

Good morning!

Today I kick off with some more Algorithms basic theory. Tim Roughgarden, the instructor, has a precise yet captivating delivery style (not too informal, not too nerdy), which makes this worthwhile.
In general, I noticed the same pattern during all of my studies: the instructor has a large responsibility in keeping the students’ heads up, in both senses.
The presentation of even the most formal of subjects has to be enriched by “refreshing” elements. For example, my Calculus 1, 2, 3 AND 4 teacher, the never-enough-celebrated G. C. Barozzi, had a way of embedding anecdotes and biographical facts about mathematicians. This both put the subject in historical context, making it feel less abstract, and relieved the audience from continued focus. Seems too nerdy still? You’ve found the wrong blog then! Ha.

I can agree that some subjects might feel a bit “dogmatic”, as formal proof of all their aspects would require a disproportionate effort from large part of the audience. In this case, it is up to the lecturer to select the more illuminating material beforehand : Longum iter est per praecepta, breve et efficax per exempla (Seneca)

So, contraction algorithms for the MINCUT problem for graphs: given a graph G = \{V, E\}, with nodes V and edges E, which is the smallest set of edges \tilde{E} that divides G in two otherwise disjoint subsets of nodes V_1 and V_2 (i.e. the smallest cutset)?

Random contraction (Karger’s algorithm)
Sequentially remove edges uniformly at random, merging the resulting nodes V(E_{k}) = V_i, V_j \rightarrow V_i (“edge contraction”) and rerouting the edges initially connected to V_i and V_j to V_i.
The cutset that remains when there are only two nodes left is a local optimum of MINCUT.
karger_random_graph_contraction
A single run of Karger’s algorithm (adapted from Wikipedia)

If N_E = |E| is the edge set size, there are N_E! possible contraction sequences. Only a subset of these yield the true MINCUT (i.e. the problem is path-dependent).