Show that an issue consisting of Clique and Impartial Set is NP Full

June 15, 2022

1

Prerequisite: NP-Completeness, NP Class, Clique, Impartial Set

Downside: Given an undirected graph G = (V, E) and an integer Ok, decide if a clique of measurement Ok in addition to an unbiased set (IS) of measurement Ok, exists. Show that it’s an NP Full.

Clarification:

A Clique is a subgraph of a graph during which the entire vertices are related, forming a whole graph. The Clique Choice Downside entails figuring out whether or not or not a clique of measurement Ok exists within the given graph.

An Impartial Set S of graph G = (V, E) is a set of vertices within the graph G = (V, E) the place no two vertices are adjoining.

Given Clique+IS drawback is a mix of each Clique and Impartial set could be described as follows:

Enter – Graph G (V, E) and integer Ok
Output – Clique and Impartial Set of measurement Ok

To show an issue NP Full, there are two steps concerned:

Show given drawback belong to NP Class

All different issues within the NP class could be polynomiial time reducible to that drawback. (That is the show of being NP-Onerous)

Now it’s not doable to scale back each NP drawback to a different NP drawback to show it’s NP completeness on a regular basis. That’s why we present that any identified NP full drawback is reducible to that drawback in polynomial time.

Proof:

1.Clique+IS belongs to NP Class:

An issue is claimed to be in NP Class if the answer for the issue could be verified in polynomial time.

Given an enter G = (V, E) and a set measurement of Ok, the reply is 2 units: I (Impartial Set) and C (Clique Set). There are three steps to confirm the answer for this drawback:

Confirm Impartial Set: For all pairs of vertices (x, y) such that x, y ∈ I and (x, y) ∉ E. This may take O(n²) time as | I | = Ok and Ok ≤ n the place n is the variety of vertices.
Confirm Clique Set: For all pairs of vertices (x, y) such that x, y ∈ C and (x, y) ∈ E. This may take O(n²) time as |C| = Ok and Ok ≤ n the place n is the variety of vertices.
Confirm Measurement of each units: To confirm |I| = |C| = ok takes O(1) time.

So, verification of an answer for Clique+IS takes at most O(n²) which is polynomial in nature so Clique+IS belongs to NP Class.

2. Clique + IS is an NP-Onerous drawback:

Now we have to present Clique + IS is at the very least as exhausting as a identified NP-Full Downside by discount approach.

Right here the identified drawback goes to be the Clique drawback which is already identified to be NP-complete which is defined in Proof of Clique being the NP-Full.

We’re going to present the discount from Clique -> Clique+IS.

Nevertheless, additionally it is doable to point out discount as Impartial Set -> Clique + IS the place it’s identified that Impartial Set is NP-Full Downside.

Enter Conversion: We have to convert the enter from Clique to enter to Clique+IS.

Clique takes an enter graph G = (V, E) and parameter Ok for set measurement. To transform the enter from Clique to Clique+IS:

We are going to create a graph equivalent to G’(V’, E’) which goes to be the copy of the given graph G = (V, E).
We’re going to add the vertices in Impartial Set I to graph G’ such that | I | = Ok and Ok ≤ n.

So, Graph G’ goes to be the graph that can have all of the vertices and edges from Graph G and vertices from the unbiased set I.

The creation of a brand new graph goes to take O(|n| + |m|) time. Including new vertices goes to take O(n). Since |I| = Ok and Ok ≤ n the place n is the variety of vertices and m are the perimeters. Thus the enter conversion could be executed in polynomial time.

Output Conversion: We have to convert the answer from Clique + IS to the answer for the Clique drawback.

Clique+IS answer yields set C, which is a Clique of measurement Ok, and set I, which is an Impartial-Set of measurement Ok.
This answer could be remodeled right into a Clique drawback answer by setting C as a Clique of measurement Ok for graph G.
We are going to take away the Impartial-Set vertices I from graph G'(V’, E’), leading to Graph G (V, E), with Clique for G equal to Clique for G’ as a result of there is no such thing as a edge distinction between G and G’.

The vertices could be dropped in O(n) since | I | = Ok and Ok ≤ n the place n is the variety of vertices, thus the output conversion could be executed in polynomial time.

Correctness: Now we have to show the correctness of the declare which says that the “Answer of Clique + IS exits iff an answer to the Clique drawback exists”.

We created a brand new graph G’= (V’, E’) from graph G within the Clique drawback, which accommodates all of the vertices and edges from graph G in addition to vertices from the unbiased set I.
Compared to graph G, no extra edges have been added in G’.
Now, if a Clique C exists in graph G'(V’, E’), it should additionally exist in graph G(V, E), as a result of the one distinction between G and G’ is the vertices from the unbiased set I, which aren’t related by any edge and therefore is not going to be a part of Clique set C.
This demonstrates that if Clique+IS has an answer, then Clique will as effectively, i.e. Clique+IS → Clique.

Additionally, as each graphs have the identical edges, if there is no such thing as a clique in graph G'(V’, E’), no clique in graph G(V, E) can exist. G’ has further vertices from the unbiased set I, however there aren’t any edges connecting them. This proved that if Clique+IS doesn’t have an answer then Clique additionally has no answer i.e., ! Clique-IS → ! Clique (¬Clique-IS → ¬Clique). This proved Clique + IS exits iff an answer to the Clique drawback exists.

Conclusion: