Prove that Sparse Graph is NP-Complete

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

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

Explanation: Sparse Subgraph problem is defined as follows:

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

To prove a problem NP Complete, there are two steps involved:

• Prove given problem belong to NP Class
• All other problems in the NP class can be polynomial time reducible to that problem. (This is the prove of being NP-Hard)

Now it is not possible to reduce every NP problem to another NP problem to prove it’s NP completeness all the time. That’s why we show that any known NP complete problem is reducible to that problem in polynomial time.

Proof:

1. Sparse Graph belongs to NP Class:

A problem is said to be in NP Class if the solution for the problem can be verified in polynomial time.

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

• For a given solution S, it takes O(|V|) time to verify that |S| =a.
• To check that the number of edges between any pair of vertices in S is at most b,  we need to run O(|V|²) algorithm. 

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

2. Sparse Graph is an NP-Hard problem:

Now we need to show Sparse Graph is at least as hard as a known NP-Complete Problem by reduction technique.

Here the known problem is going to be the Independent Set problem which is already known to be NP-complete which is explained in Proof of Independent Set being the NP-Complete.

We are going to show the reduction from Independent Set -> Sparse Graph.

Input Conversion: We need to convert the input from Independent Set to the input of the Sparse Graph.

Independent Set Input:  An undirected graph G(V, E) and integer k.
Sparse Graph Input: An undirected graph G'(V, E) and two integers a and b.

We are going to transform the input from Independent Set to Sparse Graph such that

• G’ = G(V, E) 
• a = k
• b = 0 since we need to have the maximum Independent Set

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

Output Conversion: We need to convert the solution from Sparse Graph to the solution for the  Independent Set problem.

Solution of Sparse Graph will result in a set a which would be an Independent Set of size k as k = a. So direct output from Sparse Graph can be used by Independent Set. Since no conversion is required so it’s again polynomial in nature.

Correctness:

Forward implication: Consider any Independent Set S. This is a Sparse graph as well, since there is no edges between vertices of S(b <= 0 ) and |S| = k = a

Reverse implication: A given Sparse Graph solution S, it is an Independent Set as well (number of edges between vertices is zero, and |S| = k = a.

So, this means Sparse Graph has a solution ↔  Independent Set has a solution.
The complete reduction takes polynomial time and Independent Set is an NP complete problem. So Sparse Graph is also an NP complete problem.

Conclusion:

Hence we can conclude that Sparse Graph is an NP Complete problem.

For more details, please refer:
Design and Analysis of Algorithms.