Practice Problem: Sparse Subgraph
0. Context
This is a second practice problem on NP-Completeness proofs.
The first one was Almost-SAT problem.
1. Problem Statement
Consider Sparse Subgraph problem defined as following:
Input: An undirected graph $G = (V, E)$ and variables $k, l \in \mathbb{Z}$.
Output: A set $S \subset V$ where $|S| = k$ and there are at most $l$ edges between pairs of vertices in $S$. Report NO, if no such set exists.
Prove that Sparse Subgraph problem is NP-Complete.
2. Attack Plan
We need to show that:
- $SS \in NP$
- $IS \to SS$
where SS := Sparse Subgraph problem, and IS := Independent Set problem.
3. Proof
3.1 $SS \in NP$
Consider input graph $G = (V, E)$ and $k, l \in \mathbb{Z}$ for a Sparse Subgraph problem.
Given a solution $S$, it takes $O(|V|)$ time to verify that $|S| = k$.
To check that number of edges between any pair of vertices in $S$ is $\le l$, we need to run $O({|V|}^2)$ algorithm.
3.2 $IS \to SS$
Independent Set is a known NP-Complete problem. It takes graph $G = (V, E)$ and $g \in \mathbb{Z}$ and returns $S \subset V$, where $|S| \ge g$ and $\forall x, y \in S$, $(x, y) \notin E$ i.e. there is no edges between vertices in $S$.
In order to reduce $IS \to SS$ we first need to show how input for $IS$ is transformed to input for $SS$: let’s set $k = g$ and $l = 0$. Now, run SS on input $(G, k, l)$.
Claim: $G$ has an Independent Set $S$, where $|S| = g$ $\iff$ $G$ has a Sparse Subgraph $S$, where $|S| = k = g$ and $l \le 0 $
Forward implication: take any Independent Set $S$, it is a Sparse Spargraph as well, since there is no edges between vertices of $S$ ($l \le 0$) and $|S| = g = k$.
Reverse implication: for a given Sparse Graph solution $S$, it is an Independent Set as well (number of edges between vertices is zero, and $|S| = g = k$). $\blacksquare$