Minimal Cut Problem

A cut in a graph is a partition of vertices $V$ into two non-empty subsets $A$ and $B$

A crossing edges is an edge that

  • has one end point in each of [math](A, B)[/math]
  • has tail in [math]A[/math], head in [math]B[/math] (directed)
  • if head in [math]B[/math], tail in [math]A[/math] - not a crossing edge

The problem

  • input: indirect graph [math]G = (V, E)[/math] with parallel edges allowed
  • goal: compute a cut with fewer number of crossing edges (the min cut)

Eg:

Applications

  • identify weakness/bottlenecks
  • detect communities
  • image segregation

Random Contraction Algorithm

MinCut algo:

  • while there are more than 2 vertices
  • pick a remaining edge $(u, v)$ at random
  • merge (contract) $u$ and $v$ into a single vertex
  • remove self-loogs
  • return 2 final vertices


Example:

  • step 1
  • step 2
  • step 3
  • result

Example 2:

It can find something other than a minimal cut!

  • the probability of success is just [math]\cfrac{1}{n^2}[/math]!
  • solution: repeated trials
  • try [math]N[/math] times and remember the smallest cut found


How many trials we need?

  • probability that all trials fail is [math](1 - \cfrac{1}{n^2}) ^ N[/math]
  • if [math]N = n^2 \log n[/math], [math]Pr[\text{all fail}] = \frac{1}{n}[/math]
  • running time: $\Omega(n^2 m)$
  • TODO: link to proof


Implementation

public class MinCutProblem {
    private UndirectedGraph graph;
    private UndirectedGraph initialGraphCopy;
    private int best;

    public void run() {
        graph = readGraph();
        initialGraphCopy = graph.copy();
        best = Integer.MAX_VALUE;

        int trials = 25;

        while (trials > 0) {
            iteration();
            graph = initialGraphCopy.copy();
            trials--;
        }

        out.println(best);
    }

    private void iteration() {
        while (graph.getN() > 2) {
            Pair<Integer, Integer> randomVertex = graph.randomEdge();
            graph.contract(randomVertex.getLeft(), randomVertex.getRight());
        }

        Map<Integer, List<Integer>> adjacencyList = graph.adjacencyList();

        Iterator<Entry<Integer, List<Integer>>> iterator = adjacencyList.entrySet().iterator();
        List<Integer> first = iterator.next().getValue();
        List<Integer> second = iterator.next().getValue();

        if (best > first.size()) {
            best = first.size();
        }
    }
}
public class UndirectedGraph {
    private int n;
    private final Map<Integer, List<Integer>> adj;
    private final Random random = new Random();

    public UndirectedGraph(int n) {
        this.n = n;
        this.adj = createAdjacentList(n);
    }

    private static Map<Integer, List<Integer>> createAdjacentList(int n) {
        Map<Integer, List<Integer>> res = new LinkedHashMap<Integer, List<Integer>>();

        int i = 0;
        while (i < n) {
            res.put(i, new ArrayList<Integer>());
            i++;
        }

        return res;
    }

    private UndirectedGraph(UndirectedGraph copy) {
        this.n = copy.n;
        this.adj = new LinkedHashMap<Integer, List<Integer>>();
        
        for (Entry<Integer, List<Integer>> entry : copy.adj.entrySet()) {
            adj.put(entry.getKey(), new ArrayList<Integer>(entry.getValue()));
        }
    }
    
    public UndirectedGraph copy() {
        return new UndirectedGraph(this);
    }

    public void contract(int v, int u) {
        List<Integer> newList = new ArrayList<Integer>();

        for (int fromFirst : adj.get(v)) {
            if (fromFirst != u) {
                newList.add(fromFirst);
            }
        }

        for (int fromSecond : adj.get(u)) {
            if (fromSecond != v) {
                newList.add(fromSecond);
            }
        }

        adj.remove(v);
        adj.remove(u);
        n--;

        // updating the graph so 'u' now will point to 'v'
        for (Entry<Integer, List<Integer>> entry : adj.entrySet()) {
            List<Integer> row = entry.getValue();
            for (int i = 0; i < row.size(); i++) {
                if (row.get(i).intValue() == u) {
                    row.set(i, v);
                }
            }
        }

        // and keeping only 'v'
        adj.put(v, newList);
    }

    public void addEdge(int v, int u) {
        adj.get(v).add(u);
    }

    public Iterable<Integer> adjacentTo(int v) {
        if (!adj.containsKey(v)) {
            throw new IllegalArgumentException(v + " is already removed");
        }
        return adj.get(v);
    }

    // TODO may be implemented more efficiently
    public Pair<Integer, Integer> randomEdge() {
        int[] available = new int[n];

        int j = 0;
        for (Entry<Integer, List<Integer>> entry : adj.entrySet()) {
            if (!entry.getValue().isEmpty()) {
                available[j] = entry.getKey();
                j++;
            }
        }

        int vertexU = available[random.nextInt(j)];
        List<Integer> edges = adj.get(vertexU);
        int vertexV = edges.get(random.nextInt(edges.size()));
        return Pair.of(vertexU, vertexV);
    }

    public Map<Integer, List<Integer>> adjacencyList() {
        return ImmutableMap.copyOf(adj);
    }
    
    public int getN() {
        return n;
    }
}

See also

Sources

Share your opinion