Max-Cut Problem

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 (X^*, V-X^*) such that the number of edges crossing the partition is maximized.

The algorithm presented here is based on a technique known as local search.

Algorithm:

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:

graph4

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 :-

Cut improved by flipping vertex,1
Cut improved by flipping 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 x_1 vertices in set S_1 , and x_2 vertices in set S_2 , (and x_1 > x_2 ) then flipping vertex, 1 from S_1 to S_2 would increase the size of the cut by x_1 - x_2. )

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.

|C| \geq |E|/2

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:

Arbitrary cut used as starting point for algorithm
Arbitrary cut used as starting point for algorithm

(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 :-

A Max cut for the graph
A Max cut for the graph

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“).

6 Responses to Max-Cut Problem

  1. Kaiyu says:

    Great work!
    And I still have some doubt about the “1/2 factor”. I mean the OPT can be |E| in some cases, but it can’t always be |E|, so I have some doubts about the proof about ” it produces a cut that is always within a factor of 1/2 of the optimal” .

    I read this problem in approximation algorithm and i can’t figure out a proof. Hope your response.

    • tkramesh says:

      Thanks for the comment!

      What you said is correct – OPT can |E| in some cases, but not in all cases.

      What I think I meant by “the cut produced by the algorithm is always within a factor of 1/2 of the optimal” is this : the number of edges crossing the cut our algorithm produces is >= OPT / 2.

      To see why the algorithm always produces a cut of size >= OPT / 2, look at these 2 statements:

      (Let y denote the size of the cut produced by the algorithm.)

      1. OPT = |E| / 2. (we can see this in Observation 3 in the blog post.)

      From these 2 statements, we can see that : y >= OPT / 2.

      Now, we know that OPT can at most be |E|. Therefore,

      (This was a maximization problem. Our task was to produce a cut that has as many edges as possible crossing it. Hence, an

      [ In the blog post, Observation 3 was explained cryptically. Here is a more detailed explanation as to why the size of the cut produced by the algorithm (call it ‘y’ ) >= |E| / 2.

      Now, at termination of the algorithm, we know that for every vertex, v, the number of incident edges crossing the cut is >= the number of incident edges not crossing the cut.

      i.e. for every vertex v, the number of incident edges crossing the cut is >= d(v) / 2. (where d(v) denotes the degree of vertex v). ————— (observation ‘a’)

      Now, what we want is the total number of edges crossing the cut. We take every vertex and sum up the number of incident edges crossing the cut. Now, we observe one thing that if we sum up the edges this way, we would be counting twice each of the edges that crosses the cut – once from each of the end vertices of that edge. (Therefore, we wll add a factor 1/2 in front of the summation.)

      Therefore, using “observation ‘a’ “, the number of edges crossing the cut, y, is > = 1/2 [summation over all vertices, v] d(v) / 2.
      We know that [summation over all vertices, v] d(v) = 2|E|.

      Hence, we get that : y > = |E|/2.

      • tkramesh says:

        I’m sorry – some part of my reply to your comment was missing.

        What I wanted to add is this – this was a maximization problem. Our task was to produce a cut of as large a size as possible. Say the maximum-sized cut for instance, i, is of size OPT (i). Then, an algorithm that, for all instances i, returns a cut of size >= m \times OPT (i), is called an m-approximation algorithm. (Note that m is always <= 1.) For our case, m was = 1/2. So, we have a 1/2 – approximation algorithm.

        Note that some authors might refer to what we called an algorithm with approximation factor 1/2 as an algorithm with approximation factor 2, an algorithm with approximation factor 1/3 as one with approximation 3, and so on.

  2. Kaiyu says:

    thanks for your demonstration. I get your point.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: