Scribe: Mahshid Montazer
In this lecture, we study the Max Cut problem in random graphs. We compute the probable value of its optimal solution, we give a greedy algorithm which is nearly optimal on random graphs and we compute a polynomial time upper bound certificate for it using linear algebra methods. We also study the problem of Maximum Independent Set in random graphs and we compute an upper bound to the probable value for its optimal solution.
1. Max Cut
Definition 1 Max Cut: In an un-weighted graph , a cut is defined as a partition of its vertices into two sets and . Let be the size of the cut which is the number of the edges with one endpoint in and one endpoint in . Max Cut is the the problem of finding a cut of largest size.
To give a clear example, in every bipartite graph, a bipartition is a maximum cut. It is easy to show that the size of the maximum cut would be at least half of the number of the graph edges. One question that arises here is that how much more than half of the edges can we cut. The answer is: not that much in random graphs. We will show this claim in the following section.
2. Probable Value of Max Cut Optimal Solution
In this section, we compute the probable value of Max Cut optimal solution in random graphs. Our result is for samples of , but the analysis will generalize to .
Proof: The proof is by applying Chernoff bounds on the result of lemma 2.
Lemma 4 There is a constant such that
where and the probability is taken over the choice of from the distribution .
for an appropriate choice of .
The above lemma clearly leads us to the following theorem.
Theorem 5 There is a constant such that w.h.p. Max Cut in is of size at most
Thus, we showed that in , the probable value of Max Cut is at most .
3. Greedy Algorithm for Max Cut
Consider the following greedy algorithm for Max Cut:
- if has more neighbors in than in , then
- return and
The above algorithm can be applied to any graph, but we will analyze it on random graphs. A naive analysis of the algorithm guarantees that our greedy algorithm cuts at least half of the edges, giving us an approximation ratio of 2. The reason is that at each step, we add at least half of the processing vertex’s incident edges to the cut. However, a more careful analysis of the algorithm shows that it is near-optimal for random graphs. Below, we prove our claim for .
Lemma 6 With high probability over the choice of from , the greedy algorithm finds a cut of size .
Proof: Let be the given graph and let be the order in which we process the vertices. Note that at the time of processing , we do not need to know the edges that connect to any vertex . Let and be the size of sets and before processing , respectively. Although is given before we run the algorithm, for the sake of the analysis, we can assume that we are building it on the go and while processing each of the vertices. Remember that each edge of the graph would exists independently with probability . For deciding where to put , we generate random bits and call their summation . We also generate random bits and call their summation . We put in set (respectively, ) if (respectively, ). Note that the more balanced and get, the worse it gets for the analysis. Also, note that the extra edges that the algorithm cuts other than half of the edges would be:
We know that
Thus, we have that has mean and standard deviation . Thus, with probability we have:
4. Polynomial Time Upper Bound for Max Cut
In this section, we find polynomial time upper bound certificates for Max Cut in random graphs using linear algebra techniques.
Proof: we have:
Recall that, with high probability over the choice of a graph from , if is the adjacency matrix of then we have with high probability.
We conclude that, with high probability over the choice of from we can find in polynomial time a certificate the max cut optimum of is at most .
5. Maximum Independent Set
In this section, we discuss the Maximum Independent Set problem for (especially ) and we show its close connection with Max Clique problem. Finally, we compute its optimal solution’s probable value.
Definition 8 Maximum Independent Set: In a graph , an independent set is a set of vertices that are mutually disconnected. A Maximum Independent Set in is an independent set of largest possible size. The Maximum Independent Set problem is the problem of finding such a set.
Note that the Maximum Independent Set in corresponds to the Maximum Clique in . Thus, for , everything that we argued for Max Clique is usable for Maximum Independent Set as well.
In this section, we compute an upper bound to the probable value of Maximum Independent Set’s optimal solution in .
Fix a set of size . We have
where the probability is over the choice of .
The following lemma holds.
Now, what would be the maximum value of such that with high probability we can still make sure that there exists an independent set of size ? Note that the value of (0) goes to 0 when .
A sufficient condition for is to have , showing us that there is a high probability that maximum independent set in is at most . A more careful bound is that we can have provided, say, , and so with high probability the maximum independent set in is at most . If we call , then the bound is