In this article we'll be discussing on the concept of Maximum cut problem. Firstly will understand its basic concept with Introduction. Secondly, with a graph example will deep-dive into the concept. Later we'll discuss an interesting way of finding solution with Algorithm. Lastly we'll conclude the article with application of the same.
Following are the sections of this article:-
Let us discuss what exactly is a Cut and understand the concept of it. Later we connect the dots to the end for our article Maximum Cut problem.
Cut is a partition of the vertices of a graph in to two separate or disjoint subsets. At the end we get a set called cut-set which consists of the set of edges that have one endpoint in each subset of the partition.
Formally, A Cut C = (S,T) is a partition of
V of a graph G = (V,E) into two subsets
u belongs to
v belongs to
(u,v) belongs to `E'.
The Maximum cut, as the name suggests, we want the cut that maximizes the number of crossing edges in an Undirected Graph(G).
In other words, A cut is maximum if the size of the cut is not smaller than the size of any other cut or it atleast cut's all the crossing edge in a Graph.
2. Example for Maximum Cut
Let us consider an Undirected Graph(G) as example Fig a,
Fig a - Undirected Graph(G)
From the above graph(G), there are totally 6 vertices and 8 edges in the given
Undirected Graph. Following is the Max Cut diagram Fig b for the same.
Fig b - Max Cut for
Fig b, Maximum Cut for the graph in
Fig a is 8. Only 8 edges and there is indeed a cut in which every single one of those edges crosses it. Also, the vertices
2 and 3 belongs to set T, and the vertices
0, 1, 4 and 5 take the set S. There are no edges internal to T, there are no edges internal to S. Every edge has one endpoint in each.
3. Complexity Class
Let us first discuss about computational complexity. Later we'll describe to which mainly Complexity Class this Maximum Cut problem belongs to. In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are
This Maximum Cut Problem, in generally, is computationally intractable and it'll belong to
==NP-complete problem==. More precisely, the decision version of the question where we're given a graph we want to know whether or not there exists a cut that cuts atleast a certain number of edges, that's an NP-complete problem(for which no polynomial time algorithm is known). Like most NP-complete problems, there are some computational tractable special cases. From our example (Fig a) the case of bipartite graphs. One definition of a bipartite graph is a graph in which there exists a cut, so that every single edge is crossing it.
As per my understanding their are lot of research and theories are in process to find a particular or a perfect algorithm for this problem.
We'll discuss one such approach to find the solution with an algorithm, which we have taken as a reference from the lecture notes of Carnegie Mellon University(from the notes, Section 2.1.2).
- Greedy Algorithm to find Maximum-Cut
Considering a Undirected Graph(G) formed by Vertices(
V) & Edges(
E). We start ordering on the Vertices(
V) as V1,V2,...Vn and also we have two empty
setsS, T (Where these will be having the vertices set once after cut is maximized). Pick the first vertex V1 and place it in S. For each subsequent vertex we place it in the bin or set such that |E(S,T)| is maximized.
As we are trying to maximize the cut, we initially define a
Theorem and later we
Prove the same with possible assumptions for the above Undirected Graph(G).
Statement of Theorem:
The greedy algorithm is a two-approximation algorithm for MAX-Cut.
Consider any edge in the Graph(G). One vertex must come first in the ordering. Call the later vertex as
responsiblefor forming the edge. Let Ri be the number of edges that Vi is responsible for. Since every edge has exactly one responsible vertex. So mathematically we can formulate as follows,
when Vi is added, at least (Ri/2) edges are added to the cut. Reason behind, each of the other vertices adjacent to the Ri edges that Vi is responsible for have already been assigned or placed to
binsS or T. The set which contains most endpoint vertices of these Ri edges must contain at least (Ri/2) endpoint vertices. By Greedy algorithm, Vi will be added to the other set and thus adding at least (Ri/2) edges to the cut.
Number of edges in final cut
Hence, the algorithm is a two-approximation.
At last we are at the end of the article. We have discussed a bit on the below concepts - Cut, Max-Cut, Example on the Maximum cut, Complexity Class. Also we have taken a
reference from the lecture notes of Carnegie Mellon University , which helped us in understanding the concept and to find the solution for Maximum Cut with a Greedy Algorithm.
Maximum Cut problem has many application in Industries as well as in Education or Research sector. The major application we can think of is VLSI design.
Thanks! Hope it was an informative article.