May 28, 2009 Leave a comment
This is a method by which we can prove that a combinatorial object exists with non-zero probability. The interesting thing is that we need not even find any combinatorial object in order to prove its existence.
We’ll consider 2 problems here: the max-SAT and the max-cut problem.
(1) Max-cut: Find a cut in the graph with the maximum number of edges crossing the cut.
This problem is NP-hard. But we can accomplish another thing easily. We can prove that there exists a cut with at least m/2 edges crossing it. (m and n are the edges and vertices in the graph, respectively).
How do we prove that? Simple. Use the probabilistic method.
Assign each vertex of the graph, G independently and equiprobably to one of two vertex subsets. Now, consider any edge (u,v) belonging to G. What is the probability that its ends are in different subsets? Half. (Why? Because, there are 4 cases,(1) u is in subset, A and v is in subset, B; (2) u is in subset, A, and v is in subset, A; (3) u is in subset, B, and v is in subset, A; (4) u is in subset, B, and v is in subset, B. Each of these 4 events has probability 1/4. )
So now, what is the expected number of edges of G crossing the cut? Answer: m/2 (by linearity of expectation.)
We know one simple fact: If the expected number of edges is m/2, then there exist cuts having at least m/2 edges crossing the cut. (Same as saying: if class average is 25, then someone got at least 25).
Using the above fact, what have we just proved? There exists a cut having at least m/2 edges.
(2) Max-SAT: We have a set of m clauses, each in conjunctive normal form. What is the maximum number of clauses that can be satisfied?
We wont solve that. Instead, we’ll prove that there exists an assignment of truth values such that at least m/2 clauses are satisfied.
Proof: There are n variables in all, and m clauses. Assign truth values independently and equiprobably to each variable. Consider any one clause which has k variables. What is the probability that this clause is not satisfied? Answer: At most 2^(-k).
So, the probability that the clause is satisfied is at least 1 – 2^(-k), which is greater than or equal to 1/2.
Again, by linearity of expectation, the expected number of satisfied clauses is at least m/2.
Using the probabilistic method, we’ve proved the existence of two combinatorial objects. For more on this, read Ch. 5 of Randomized Algorithms by Motwani and Raghavan.