Due to the ever-increasing deployment of graph theory in natural and artificial phenomena, it is challenging for scientists to utilize it in a more performant manner. One of the most popular topics in graph and networking theory, the authors try to provide a practical approach to minimum cut algorithms.

The paper presents a heuristic and randomized algorithm for the minimize cut problem with claimed running time O(n+m), for a graph with n vertices and m edges, when run sequentially. The authors adapt Raghavan et al. and Padberg-Rinaldi’s algorithms for clustering, contracting, and reducing the input graph, using a label propagation technique that finds almost optimal minimum cuts in a graph with acceptable running time, scalability, and error rate.

In an incoherent discussion based on edge contractions, the authors introduce a parallel heuristic minimum cut algorithm: VieCut. Speeding up Karger and Stein’s algorithm to contract large numbers of edges, deploying Padberg and Rinaldi’s method for final reduction, and using tools from Nagamochi et al. to find the minimum cut of contracted graphs are the main topics. Experimental results follow a confusing theoretical discussion about the proposed algorithm. According to the authors, these results contain more structured material and demonstrate the supremacy of the proposed algorithm in comparison with other competitors.

The main value of the paper is its significant investigation; unfortunately, however, its structure is confusing and there is no closure in the theoretical discussion. The reliability of the proposed algorithm in terms of pseudocode and claimed running time is seriously arguable; although many issues are mentioned, the details of the algorithm are not clear. While the paper doesn’t do a good job of developing the theoretical topics, its experimental results are noteworthy.