Conditions: NP-Completeness, NP Class, Dense Subgraph
Drawback: Given graph G = (V, E) and two integers a and b. A set of a variety of vertices of G such that there are at the very least b edges between them is named the Dense Subgraph of graph G.
Clarification: To show the Dense Subgraph downside as NP-completeness by generalization, we’re going to show that it’s a generalization of the recognized NP-complete downside. On this case, we’re going to take Clique because the recognized downside which is already recognized to be NP-complete, and defined in Proof of Clique Is an NP-Full and we have to present the discount from Clique → Dense Subgraph.
Clique is a subset of vertices of an undirected graph such that each two distinct vertices within the clique are adjoining.
Proof:
1. Enter Conversion: We have to convert the enter from Clique to the enter of the Dense Subgraph.
Clique Enter: An undirected graph G(V, E) and integer okay.
Dense Subgraph Enter : An undirected graph G'(V, E) and two integers a and b.
We’re going to rework the enter from Clique for Dense Subgraph such that
- G’ = G(V, E)
- a = okay
- b = (okay * (okay – 1))/2
This conversion goes to take O(1) time so it’s polynomial in nature.
2. Output Conversion: We have to convert the answer from Dense Graph to the answer for the Clique downside.
Answer of Dense Graph will lead to a set a which might be a Clique of dimension okay as okay = a. So direct output from Dense Graph can be utilized by Clique. Since no conversion is required so it’s once more polynomial in nature.
3. Correctness: We now have restricted the vary of enter worth b such that (okay¦2) with worth as (okay * (okay – 1))/2.
Now we’re searching for a subgraph having okay vertices and are related by at the very least (okay * (okay – 1))/2 edges.
- Since in a whole graph, n vertices can have at most (n * (n – 1))/2 edges between them so we will say that we have to discover a subgraph of okay vertices which have precisely (okay * (okay – 1))/2 edges which suggests output graph ought to have an edge between every pair of vertices which is nothing however Clique of okay vertices.
- Equally, a Clique of okay vertices on a graph G(V, E) will need to have (okay * (okay – 1))/2 edges which is nothing however the Dense-Subgraph of graph G(V, E)
Crimson Edges and Vertices denotes a Dense-Subgraph with a = 4 and b = 5
So, this implies Dense-Subgraph has an answer↔ Clique has an answer.
The whole discount takes polynomial time and Clique is NP full so Dense Subgraph can be NP full.
Conclusion:
Therefore we will conclude that Dense-Subgraph is NP Full
