What is the difference between min- cut formulation and (bi) partitioning formulation?

Operations Research Asked by fathese on January 8, 2021

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?

One Answer

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.

Answered by LocalSolver on January 8, 2021

Add your own answers!

Related Questions

Multiple Knapsacks with splitting

1  Asked on December 20, 2021 by cesar-canassa


How to simulate computational execution time?

2  Asked on August 19, 2021 by matheus-digenes-andrade


Parallel nonlinear solvers

3  Asked on August 19, 2021 by josh-allen


Error evalution for linear fits

1  Asked on August 19, 2021 by jane


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP