Vertex Cover as NP-Complete

Vertex cover of Graph G = (V, E) is set of vertices such that any edge (u, v) ∈ E, incident to at least one vertex in the cover. In other words, vertex cover is a subset of vertices V’ ∈ V such that if the edge (u, v) ∈ E then u ∈ V’ or v ∈ V’.

The size of the cover is a number of vertices in V’. Vertex cover problem is to find out such minimum size cover. A decision problem is to check if given graph has vertex cover of size k.

• The simplest way of finding the vertex cover of graph G = (V, E) is to randomly select the edge (u, v) ∈ E and delete adjacent edges of u and v. Repeat the procedure until the cover is found. For example, consider the following graph.

• Let S represents the solution set. Initially, S = { }

Step 1: Select any random edge, let us select the edge

<1, 2> as shown in the Fig. 8.5.2. Remove the incident edges of vertex 1 and 2.

So, S = {1, 2}

• Still few edges are not adjacent to vertices in S, so go on.

Step 2 : Let us now select edge <5, 6>. Remove adjacent edges to vertex 5 and 6.

So, S = {1, 2, 5, 6}

• Still few edges are not adjacent to vertices in S, so go on.

Step 3 :  Let us now select the edge <3, 7>. So

S = {1, 2, 3, 5, 6} and all the edges are adjacent to at least one vertex in S.

So S is the cover of graph G.

However, S is the cover of the graph but it may not be the minimum. Instead of selecting edge <5, 6> in step 2, if we would have selected edge <3, 6>, it would have resulted in a minimum number of vertices.

Theorem: Vertex cover is NP-complete

Proof:

To demonstrate that Vertex Cover is NP-complete, we must first demonstrate that the problem can be represented in NP and that it can be reduced to an NP-hard form using an NP-complete problem.

To begin, we will demonstrate that it is possible to have Vertex Cover in NP. A collection of vertices that completely covers the graph’s edges would be eligible for the Vertex Cover certificate. It is not difficult for us to determine, in a timescale that is polynomial, whether or not a particular set of vertices covers all of the edges in the graph. As a result, NP contains the Vertex Cover.

The next step is to demonstrate that an NP-hard problem, such as Vertex Cover, can be reduced to an NP-complete problem, such as 3SAT. The reduction will demonstrate that it is possible to convert an instance of 3SAT into an instance of Vertex Cover in a time that is polynomial.

If we have an instance of 3SAT with n variables and m clauses, then the following steps should be taken to construct a graph G with 2n vertices and 3m edges:

• Create two vertices, one positive and one negative, for each variable xi. These vertices will represent the positive and negative occurrences of x_i, respectively.
• Create a triangle with three vertices labelled u_j, v_j, and w_j for each clause C_j in the sentence.
• Add an edge between v_i‘ and either u_j, v_j, or w_j, depending on whether x_i appears positively, negatively, or not at all in C_j, for each clause C_j that contains the literal x_i. This edge should be present for each clause C_j that contains x_i.
• Add an edge between v_i and either u_j, v_j, or w_j, depending on whether x_i appears negatively, positively, or not at all in C_j, for each clause C_j that contains the literal ¬x_i. This applies to each clause C_j that also contains the x_i.

It is possible to complete the construction of graph G in a polynomial amount of time. We will be able to demonstrate that this graph possesses a vertex cover of size k if, and only if, the initial instance of 3SAT can be satisfied.

Let’s say that the first instance of 3SAT is satisfiable, meaning that there is a satisfying assignment that can be used to assign values to all n variables. We are able to construct a vertex cover with the size k = 2m + n by including all of the vertices that correspond to the literals in the clauses that were satisfied, as well as all of the vertices that correspond to the variables that were assigned true.

On the other hand, let us assume that G possesses a vertex cover with the size k = 2m + n. It is possible for us to demonstrate that this vertex cover must contain precisely one vertex from each triangle that corresponds to a clause C_j. Since there are three vertices in each triangle, there must be exactly three vertices in the vertex cover that come from each clause. This is a requirement. In addition, we are able to demonstrate that the vertex cover must contain exactly a single instance of either v_i or v_i‘ for each variable x_i. If both v_i and v_i‘ were to be included, we would need to include at least one of u_j, v_j, or w_j for each clause C_j that contains x_i or ¬x_i; however, doing so would result in a vertex cover that is at least 3m + 2n in size, which is greater than k. Therefore, depending on whether x_i or ¬x_i is included in the cover, the vertex cover must include exactly one of v_i or v_i‘ for each variable x_i. This requirement applies regardless of whether x_i or ¬x_i is present. After that, we are able to construct an assignment that satisfies our needs by giving the value true to the variables that correspond to the vertices in the cover that correspond to vi and giving the value false to the variables that correspond to the vertices that correspond to v_i‘. This will give us the result that we are looking for.

This reduction demonstrates that Vertex Cover is an NP-hard problem, and given that we have already demonstrated that it falls within NP, it follows that Vertex Cover is an NP-complete problem.

---

YouTube Channel: CodeCrucks