Thursday, June 1, 2023
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 quite a few vertices of G such that there are at most b edges between them is called the Sparse Subgraph of graph G.

Clarification: Sparse Subgraph drawback 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 drawback belong to NP Class
  • All different issues within the NP class may be polynomial time reducible to that drawback. (That is the show of being NP-Arduous)

Now it’s not attainable 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.


1. Sparse Graph belongs to NP Class:

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

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

  • For a given resolution 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 drawback:

Now we have to present Sparse Graph is not less than as exhausting as a identified NP-Full Drawback by discount approach.

Right here the identified drawback goes to be the Impartial Set drawback which is already identified 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 drawback.

Answer of Sparse Graph will end in a set a which might be an Impartial Set of dimension 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 properly, since there isn’t any edges between vertices of S(b <= 0 ) and |S| = ok = a

Reverse implication: A given Sparse Graph resolution S, it’s an Impartial Set as properly (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 drawback. So Sparse Graph can be an NP full drawback.


Therefore we will conclude that Sparse Graph is an NP Full drawback.



Please enter your comment!
Please enter your name here

Most Popular

Recent Comments