CODEWITHSUNDEEP
algorithmgraph
Leo S
Leo S

Reputation: 339

Detecting the existance of the cut

we have an undirected graph G = (V,E) with n nodes and m edges, i want to calculate whether G have a cut of size m or not ? How can I solve it ? I tried BFS but i realized that we can calculate with lower or upper level for cut.

Edit: The cut just separates the graph in two pieces.

Upvotes: 1

Views: 147

Answers (1)

Moritz Groß
Moritz Groß

Reputation: 1490

This problem is a sub-case of the maximum cut problem. Note that the maximum-cut problem asks for a cut of at least an arbitrary value x, not necessarily m. It is thus more general than what you asked for.

Max-Cut is NP-complete, meaning that there is no known algorithm in polynomial time. The best know algorithm is trying out every possible cut (brute search).

A max-cut may look like the following picture. Generally it does NOT look like something that you'd create with BFS or DFS.

maximum cut in a small graph

In this sub-problem you are lucky though: First off, the edges are unweighted, meaning that indirectly all of them have a weight of 1. If they were weighted, my proposed solution would be invalid.

If there is a max-cut of size m, this means that every edge is part of the cut. This is equivalent to the test of bipartness. This is possible to check in linear time. Here is an example of a biparte graph: a biparte graph

To conclude: The question "does Graph G have a cut of size of at least x" is NP-complete, but your question is equivalent to test of bipartness. A graph is biparte exactly if it doesn't contain any circles of uneven length. Here is the algorithm to test for bipartness, which runs in O(V+E), just like BFS.

Upvotes: 1

Related Questions