September 29, 2009 6 Comments
The Maximum Cut Problem asks us to find an edge-cut of maximum cardinality. (We are considering undirected, unweighted graphs.) In other words, we are required to find a partition of the vertex set, V into such that the number of edges crossing the partition is maximized.
The algorithm presented here is based on a technique known as local search.
Take any arbitrary partition of the vertex set, (X, V-X). Find a vertex which when flipped to the other set of the partition would have more of its incident edges crossing the cut.
Flip the vertex to the other set of the partition. Continue searching for such a vertex in this new partition. Continue this procedure generating new partitions until no such vertex satisfying the above condition exists.
Consider this example:
We are given an arbitrary cut as shown above. Consider vertex, 1. Out of its 3 incident edges, 2 are incident on vertices of S1 (its current set), and one is incident on a vertex of set S2. Hence, by moving vertex, 1 to set, S2, we can improve the cardinality of the cut by one.
This is what we get by moving vertex,1 :-
Observations on the algorithm:
1. Each “flip” of a vertex from one set of the partition to the other increases the size of the cut by at least one. (If vertex, 1 is incident on vertices in set , and vertices in set , (and ) then flipping vertex, 1 from to would increase the size of the cut by )
2. The above point shows why the algorithm runs in polynomial time. The maximum possible size of a cut of G=(V,E) is |E|. From Observation 1, we can conclude that the algorithm makes at most |E| flips. Further, each flip can be done in polynomial time. Hence, the algorithm is of polynomial time complexity.
3. What is the minimum number of edges that the algorithm returns in its cut? In other words, give a lower bound on the size of the cut returned by the algorithm.
This is simple to compute.
Let (X, V-X) be the cut returned after the termination of the algorithm. (Termination of the algorithm implies that flipping any vertex from one set of the partition to the other would not produce a better cut.)
Consider any vertex, v in this cut. At least half of the edges incident on vertex, v in graph G would be crossing (X, V-X). (since otherwise it would mean that flipping v would improve the cut returned by the algorithm, indicating that the algorithm has not yet terminated i.e. contradiction.)
Therefore, at least half of all edges of G cross the cut returned by the algorithm.
where |C| represents the size of the cut returned by the algorithm.
4. Consider the following example:
For the above graph, let an arbitrary cut be given by:
(Edges within sets S1 and S2 have been omitted for clarity.)
If we start our algorithm with this cut as a starting point, we find that we can find no vertex which is suitable for flipping. ( Consider vertex, a: Flipping it would make it incident on n/2 vertices of S1. But it is already incident on n/2 vertices on S2. Flipping it will not improve the cut. Same is the case with vertex, b. Similarly flipping any of 1,2,..,n would improve the cut.)
Hence, this is the best cut that the algorithm can produce when provided with this particular cut as a starting point.
Size of cut produced by algorithm = n
But this is certainly not a maximum cut for the graph. Consider the following cut :-
Size of above cut = 2n.
This is clearly the maximum cut possible for the graph, since |E| itself is 2n.
Hence, our algorithm produces a cut that is factor of 1/2 of the optimal in this particular instance.
( Please note that the output of the algorithm for a particular input graph varies according to the arbitrary cut that is chosen as its starting point. )
5. The best possible cut can be of size |E|.
From Observation 3, it is known that the algorithm produces a cut of size at least |E| / 2.
Hence, the algorithm is a factor- 1/2 approximation algorithm. (i.e. it produces a cut that is always within a factor of 1/2 of the optimal)
Observation 4 indicates that the factor of 1/2 is indeed a tight bound on the performance of the algorithm through an example where the algorithm performs no better than than a factor of 1/2. (Such examples are known as “tight examples“).