# Vertex Cover as NP-Complete

Vertex coverof Graph G = (V, E) is set of vertices such that any edge (u, v) ∈ E, incident toat least onevertex 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’orv ∈ V’.

The size of the cover is a number of vertices in V’.

Vertex cover problemis 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