
https://en.wikipedia.org/wiki/Minimum_k-cut
http://www.ccs.neu.edu/home/austin/papers/multicut.pdf


Vazirani:  
    http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf
    4 - MultiwayCut and k-Cut ................................. 38
    18 - Multicut and Integer MulticommodityFlow in Trees ..... 146
    19 - MultiwayCut ............................................ 155
    20 - Multicut in General Graphs .............................. 168
    21 - Sparsest Cut .............................................. 180


Minimum K-cut -
    * Find the minimum weight set of edges such that there are $k$ connected compoments. $k$ is part of the input.
    * This has a 2 - 2/k approximation.
    
    Polynomial if $k$ is fixed, but NP-hard if $k$ is considered part of the
      input.
    The previous sentense is misleading.
    This does not mean $k$ is found, you always specify $k$.
    Running time is $O(|V|^{k^2})$

Multiway Cut - 
    * Subclass of multicut
    * Given a set of terminals S = (s1, s2, ..., s3) find the minimum weight
      set of edges that disconnects the terminals.
    * This has a 2 - 2/k approximation. THere is also a 3/2 approximation.

Multicut - 
    Given pairs of terminals ((s1, t1), (s2, t2), ... (sk, tk)) - find minimum weight set of edges that
    disconnects each s from its corrsponding t.  Each pair is disinct, but
    verticies within pairs are not required to be distinct.


    * Generalizes multiway cut
    * Dual of Integer multicommodityflow
    * has O(log k) approximation

k-Multicut - 
    same as multicut, but at least k pairs are separated.

Sparset Cut -
    Let G = (V,E) be an undirected graph
    with capacities, source–sink pairs, and demands defined as in Problem 21.1.
    The sparsity of cut (S, S) is given by c(S)/dem(S). 
    The problem is to find a cut of minimum sparsity
