Vertex Cover and Set Cover – 3

Consider the Vertex Cover problem.

To recapitulate:
Given: Undirected graph, G = (V, E), positive integer, k.
Question: Does G have a Vertex Cover of size at most k?

Now, we shall look at a problem related to the above question.

How do we verify the validity of a answer to the Vertex Cover problem?

Consider the following example graph, G = (V, E):

vertex_cover2

Consider the following conversation between a teacher and a student.

Teacher: Does the above graph have a Vertex Cover of size \leq 5 ?
Student: Yes
Teacher: Give me some proof of your answer that I can check quickly.
Student: Consider the set of vertices: X=  {v3, v5, v7}.This set is a Vertex Cover of G of size \leq 5 .

The teacher needs to check 2 things now:
(1) Is the size of set X \leq 5 ?
(2) Is set X a Vertex Cover of the graph?
If the answer to both of the above questions is “yes”, then the student’s answer has been validated.

Both these questions about set, X can be answered quickly.

That is obvious for the first question. You need to find out the size of the set, and compare that with 5.

For the second question: We will check for each edge whether that edge is covered by X i.e. whether at least one of its end points is in X. This can also be done quickly. [Checking for a particular edge requires time proportional to the size of X. We need to check this for all edges of G. Hence, this can be done in time O(|E|.|X|).]

What we observed here is a very important concept related to complexity theory.

We are given a decision problem (i.e. a problem whose answer is “yes” or “no”). If we are able to provide a “short and efficiently-verifiable proof” of the answer, when the answer is “Yes”, then the problem is said to belong to a class of problems called as NP.

Notes:

1. What is meant by “short proof”?
“Proof” is also termed as “Certificate”. A “short” certificate means that the size of the certificate is bounded by a polynomial in the input size. For the Vertex Cover problem, the input is the graph G = (V, E) and the positive integer, k. So, a certificate whose size is bounded from above by a polynomial in |V|, |E|, and k, is said to be a “short” certificate.

2. What is meant by “efficiently-verifiable proof/certificate”?
Using the certificate, we should be able to prove or disprove the answer to the decision problem in a time that is polynomially bounded in the input size.When the answer to the Vertex Cover problem is “Yes”, a short and efficiently-verifiable certificate is a set of vertices of cardinality \leq k that forms a vertex cover of the input graph.

3. Problem vs. Instance of a problem: The Vertex Cover problem and the Set Cover problem are examples of problems. An instance of a problem is different. For the Vertex Cover problem, an instance of the problem is a particular graph G = (V, E) and a positive integer, k. For example, the graph drawn above and question asked by the teacher setting k=5, formed one particular instance of the Vertex Cover problem.

“Yes” instance: If the answer to a particular instance of a decision problem is “Yes”, then it is called a “yes”-instance of the problem.

“No” instance: If the answer to a particular instance is “No”, then that instance is termed as a “no”-instance of the problem.

4. NP stands for Non-deterministic Polynomial time. This means that the answer to a “yes”-instance of a decision problem in NP can be verified in polynomial time. (In other words, there exists a short and efficiently-verifiable certificate for every “yes”-instance of a problem in NP.)

—–

Let us continue the teacher-student conversation from above.

Teacher: Does the given graph have a Vertex Cover of size \leq 2 ?
Student: No.
Teacher: Give me a short and efficiently-verifiable certificate for your answer.

A possible certificate for this would be to enumerate all possible sets of vertices of size \leq 2 .

There are n(n-1)/2 + n such sets. (Here, n = |E|.)

The general Vertex Cover problem instance has input parameters as |V|, |E| and k. If the instance turns out to be a “no”-instance, a certificate on the lines of the one given above would include all sets of vertices of size \leq k . (We can also use sets of vertices of size exactly k as certificate. The cases for sets of smaller size get covered by sets of size exactly k.) Number of such sets (of size exactly k) is (n choose k) which is NOT polynomially bounded in n and k. Hence, this is not a short certificate.

In order to verify the validity of the answer (which was “no”) using the abover certificate we will have to consider all suts of size k, and check whether any of those is a Vertex Cover. Checking for a particular set takes polynomial time. But since we need to check for all sets to validate the answer, verifying this certificate takes time that is not polynomially bounded in the input size. Hence, this is not an efficiently-verifiable certificate.

Notes:

5. We observe a dichotomy between “yes”-instances and “no”-instances of the Vertex Cover problem. We can efficiently verify the answer to a “yes”-instance of the Vertex Cover problem. But, doing the same for a “no”-instance seems to be difficult. Note that we are not saying that it is impossible. Simply, that efficient answer verification for a “no”-instance of the Vertex Cover problem is not known as yet. It is an open problem. Solving this would solve a celebrated open question in complexity theory: Is NP = co-NP?  [co-NP is the class of problems for which the “no”-instance can be verified efficiently.]

Points to ponder:

1. Prove that the Set Cover problem belongs to NP.

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: