I have a min-cut formulation and a bi-partitioning problem. The two problems focus on finding the minimal cut value separating the two partitions? So what are really the differences between the problems? what are mainly the considered objectives and constraints?


1 Answer 1


Roughly speaking, in minimum cut problems, the goal is generally to find a minimum cut (possibly weighted) between two fixed sets of vertices, called the sources and the sinks. Given one source and one sink in input, the problem can be solved in polynomial time, a famous theorem in combinatorial optimization.

On the other hand, in graph partitioning problems, the goal is generally to find a partition of the vertices into subsets with a maximum size while minimizing the cut (possibly weighted) between these subsets. For example, the bisection problem consists of finding a partition of the vertices into two subsets of equal size, while the minimum cut between the two subsets is minimum. This problem is known to be NP-hard.

But in the end, this is a matter of precise definition of the problem to be solved. Some cut problems are polynomial; some others are NP-hard (for example, the so-called maximum cut problem). The same holds for graph partitioning problems.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.