A cut is defined as a partition of vertices of a graph.  There may exist lots of algorithms related to cuts of graphs, we only summarize min-cut algorithm and its GPU parallelization.

Min-cut algorithm

Min-cut algorithm finds a partition {S, T} of vertices with the minimum sum of edge weights in a cut-set c(S, T) = {(u, v) | u∈ S, v ∈ T}. In this report, we only consider st min-cut problem, which is that we are also given two nodes, s ∈ S and t ∈ T.

Problem of finding st min-cut can be converted to its dual problem, which is a max-flow problem (max-flow min-cut theorem). Given a graph with edge capacities u(e) and a source node s and a sink node t, max-flow problem is to find the maximum possible flow from s to t.

A flow f(e) of an edge e must satisfy these constraints:

• 0 ≤ f(e) ≤ u(e)
• flow leaving a vertex v = flow entering a vertex v (v ≠ s, t)

given the solution of max-flow algorithm, the solution of min-cut algorithm can be easily obtained by removing saturated edges from graph. After edge removal, the nodes reachable from s are assigned to the partition S, and remaining nodes are assigned to T.

Edmond-Karp Method

This algorithm is a specialization of Ford-Fulkerson algorithm. Although this algorithm is similar to Ford-Fulkerson algorithm, this algorithm also runs when edge weights are not integers. Given an initial graph, we start from flow=0 and "fill" flow on a path from s to t. We repeat this process until we have no more possible path from s to t. The simplified algorithm outline is as follows:

1. Repeat while there is no more possible path from s to t:

   1. find the shortest path from s to t (use BFS or anything).
   2. subtract the capacity(or edge weight) from the capacities of edges on the path

The time-complexity of this algorithm is O(VE²).

Goldberg's Push-Relabel Algorithm

As we can infer from the name of the algorithm, we perform two types of operations on each nodes: push and relabel.

In this algorithm, we only 'push' from a node u to v when 'height' of u is higher than v. Therefore, we give | V | and 0 for height of s and t (the longest path from s to t is at most | V | long).

A push from a node u to v is an operation sending a flow from u to v and it is only performed when node u and v satisfy all of the conditions below:

• The flow entering u is larger than flow leaving u. (i.e. excess(u) > 0)
• Edge capacity from u to v is nonzero.
• u is higher than v.

If all these three conditions are satisfied, the maximal possible value of flow is sent to u to v.

Relabeling is a process of reassigning height of each node. This is done when the conditions below are all satisfied:

• The flow entering u is larger than flow leaving u.
• u is higher than any other v that edge (u, v) is not saturated.

then the height of u is set to a minimal value that satisfies height(u) > height(v).

Given these two operations, the algorithm outline of Push-Relabel algorithm becomes simple as below:

1. While we have a node that is available for Push or Relabel:

   1. Perform push
   2. or perform Relabel.

The time-complexity of this algorithm is known to be O(V²E)

GPU-Parallelization of Push-Relabel Algorithm

As both Push and Relabel operations are local operations, parallelized version of st min-cut algorithm can be implemented using Push-Relabel algorithm.

Most naïvely, we can run a thread for a node. Each thread will perform Push and Relabel operation. However, this will not work because of the synchronization problem. It is because the operation on a node effects the neighboring nodes.

To avoid synchronization problem, Vivhab Vineet and P. J. Narayanan divided Push operation into Push and Pull kernels.

• In a Push kernel, each node pushes flows to its neighbors. the flows are stored in separate variables to prevent read/write conflicts.
• In a Pull kernel, the results of Push kernel is collected and applied to each node. Excess flow of each node (excess(u)) is calculated.

If hardware allows atomic add operations, Push and Pull can be performed in a single kernel without read/write conflicts. Implementation like this will lessen the global memory access and lead to the fast convergence.

However if hardware does not support atomic operations, Push kernel and Pull kernel must be separated.