Friday, August 12, 2022
HomeSoftware DevelopmentShow that Sparse Graph is NP-Full

Show that Sparse Graph is NP-Full

Prerequisite: NP-Completeness, NP Class, Sparse Graph, Impartial Set

Drawback: Given graph G = (V, E) and two integers a and b. A set of numerous vertices of G such that there are at most b edges between them is called the Sparse Subgraph of graph G.

Rationalization: Sparse Subgraph downside is outlined as follows:

  • Enter: An undirected graph G = (V, E) and variables a, b
  • Output: A set S which is a subset of V the place |S| = a  and there are at most b edges between pairs of vertices in S. Report “NO”, if no such set exists.

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

  • Show given downside belong to NP Class
  • All different issues within the NP class might be polynomial time reducible to that downside. (That is the show of being NP-Arduous)

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


1. Sparse Graph belongs to NP Class:

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

Given an enter G = (V, E) and two integer variables a and b.

  • For a given answer S, it takes O(|V|) time to confirm that |S| =a.
  • To verify that the variety of edges between any pair of vertices in S is at most b,  we have to run O(|V|2) algorithm. 

So, verification of an answer for Sparse Graph takes at most O(|V|2) which is polynomial in nature so Sparse Graph belongs to NP Class.

2. Sparse Graph is an NP-Arduous downside:

Now we have to present Sparse Graph is no less than as laborious as a recognized NP-Full Drawback by discount method.

Right here the recognized downside goes to be the Impartial Set downside which is already recognized to be NP-complete which is defined in Proof of Impartial Set being the NP-Full.

We’re going to present the discount from Impartial Set -> Sparse Graph.

Enter Conversion: We have to convert the enter from Impartial Set to the enter of the Sparse Graph.

Impartial Set Enter:  An undirected graph G(V, E) and integer ok.
Sparse Graph Enter: An undirected graph G'(V, E) and two integers a and b.

We’re going to rework the enter from Impartial Set to Sparse Graph such that

  • G’ = G(V, E) 
  • a = ok
  • b = 0 since we have to have the utmost Impartial Set

This conversion goes to take O(1) time. So it’s polynomial in nature.

Output Conversion: We have to convert the answer from Sparse Graph to the answer for the  Impartial Set downside.

Answer of Sparse Graph will lead to a set a which might be an Impartial Set of measurement ok as ok = a. So direct output from Sparse Graph can be utilized by Impartial Set. Since no conversion is required so it’s once more polynomial in nature.


Ahead implication: Take into account any Impartial Set S. This can be a Sparse graph as effectively, since there isn’t a edges between vertices of S(b <= 0 ) and |S| = ok = a

Reverse implication: A given Sparse Graph answer S, it’s an Impartial Set as effectively (variety of edges between vertices is zero, and |S| = ok = a.

So, this implies Sparse Graph has an answer ↔  Impartial Set has an answer.
The entire discount takes polynomial time and Impartial Set is an NP full downside. So Sparse Graph can be an NP full downside.


Therefore we are able to conclude that Sparse Graph is an NP Full downside.



Please enter your comment!
Please enter your name here

Most Popular

Recent Comments