Given a graph, a Vertex Cover, is a set of nodes such that all edges in the grap

Question

Given a graph, a Vertex Cover, is a set of nodes such that all edges in the graph are incident to at least one node in the set. Thus, in the following graph of a 3-diniensional hypercube, the node set { A, C, F. H } forms a vertex cover. Prove that the problem Given a graph, does it contain a Vertex Cover of K nodes? is NP-Complete. There are two steps to the proof. First show that it is an NP problem. Second, show that a known NP-Complete problem reduces to it. That is, show that a known NP-Complete problem can be changed to a VERTEX_COVER problem in such a manner that the two problems give the same answer for their respective inputs. You also need to show that this transformation can be done in time that is polynomial in the size of the input. Note that we have shown 3 problems to be NP-Complete: SAT, CLIQUE, and INDEPENDENT_SET. One of these problems can easily be reduced to VERTEX_COVER. Show that VERTEX_COVER is in NP. Show that a known NP-Complete problem can be transformed to a

Explanation / Answer

Showing Vertex Cover is NP

A problem is in NP if you can quickly (in polynomial time) test whether a solution is correct (without worrying about how hard it might be to find the solution).

For proving, we argue that there is polynomial time verier for X, which, given a solution (certicate), will
verify in polynomial time, that, it is a solution.

To show VERTEX-COVER is in NP, we choose the certicate as "the vertex cover of size k".

Since we know that SAT is NP-Complete, we reduce an instance of SAT, say $, to a graph G and an
integer k so that $ is satisable whenever G has a vertex cover of size k.

Show that a known NP-Complete problem can be transformed to a VERTEX_COVER problem.

For the reduction, we are going to take an instance of 3SAT (a boolean formula) and reduce it to a vertex cover instance that has a cover if and only if the 3SAT formula has a satisfying assignment. The first thing we will do is force a choice for each variable to either True or False by having a pair of vertices for every literal and it's negation. So an xi in U will yield two vertices in G.

Next, we create a 'gadget' to represent the clauses. What we will do is for each clause (xi, xj, xk) we'll create a three vertex triangle where the each vertex is connected to the other two and to the corresponding literal from the section above.

Finally, we must choose an appropriate K for the instance of VERTEX COVER. We'll choose l + 2m where l is the number of literals and m is the number of clauses.

So, if there is a satisfying assignment of the boolean 3SAT formula, then we can make the True literals part of our vertex cover in G. That's l nodes of our cover. Also, by choosing one node for every literal, we've covered the edge between them. Next, notice that since we've satisfied the 3SAT formula, we have to have chosen at least one of the literals in each clause to be True indicating that in each triangle gadget we have at least one node whose outgoing edge (the one going outside the gadget) is covered. Now, we need only two vertices (or less) from each triangle to cover the rest of the edges. This yields at most 2m more vertices, for a maximum total of l + 2m vertices in our cover.

Next, assume there's a vertex cover of G with l + 2m vertices or less. We know at least l vertices are covering the literal pairs since the edge between them can't be covered in any other way. The other 2m vertices (or less) must be covering the triangles since each triangle requires two vertices to be covered. We take the literal nodes in the vertex cover to be our assignment of the formula. This assignment has to satisfy the formula since every clause is satisfied by our gadget's construction. Hence, we have successfully transformed 3SAT (which is known to be NP complete) to Vertex Cover.

Show that this transformation can be done in time that is polynomial in the size of
the input.

This contruction takes as input the m clauses and l literals and creates a graph with exactly 2l + 3m nodes. This can easily be done in polynomial time. This also proves that VERTEX COVER is NP-complete.

Show that the two problems give the same answer for their respective inputs

From the second part of the same question, this is pretty obvious.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.