## 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$