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:

1. $SS \in NP$
2. $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$