NP-completeness proofs (3): set-related problems

25 Apr, 2025

In this article, we’ll explore three fundamental NP-completeness proofs involving set-based problems: set cover, partition, and subset sum. These proofs demonstrate elegant reductions between different computational problems and provide insights into the nature of NP-completeness. — At least, I hope it do provide insights to you. 😆

Have fun proving them by yourself!

P1: Set cover problem

Definition.

Set cover decision: Given a set of elements $U$, a collection $S$ of subsets of $U$, and an integer $k$, does there exist a selection of $k$ or fewer sets from $S$ whose union equals $U$?

Proof by reduction from vertex cover.

1. Certificate: Verifying $m$ sets of $n$ elements would costs $O(nm)$, which is in polytime. Thus the problem is NP.

2. Vertex cover decision: Given a graph $G(V,E)$ and an integer $k$, does there exist a subset of vertices $S\subseteq V$ such that $|S|\le k$ and for each edge $(u,v)\in E$, at least $u$ or $v$ belongs to $S$?

3. Reduction: Let $U=E$. For each vertex $u$, put all edges connected to $u$ into a set $S_u$.

   Given an algorithm to find a set cover of size $k$ that covers $U$, i.e. covers all edges in the graph, then we can pick either $u$ or $v$ for each edge $(u,v)\in E$ to form a vertex cover of size $k$.

4. The construction of set cover inputs costs $O(|V|\cdot |E|)$ since we are iterating through all edges connected to all vertices. This reduction is in polytime. In conclusion, the set cover decision problem is NP-complete.

P2: Partition problem

Definition.

Partition decision: Given a set of integers $S$, can it be partitioned into two subsets $A$ and $\bar{A}$ such that $\bar{A}=S-A$ and ${\displaystyle {\sum }_{x\in A}x={\sum }_{x\in \bar{A}}x}$ ?

Proof by reduction from subset sum.

1. Certificate: Calculating ${\displaystyle {\sum }_{x\in A}x}$ and ${\displaystyle {\sum }_{x\in \bar{A}}x}$ are both $O(n)$, so verification is in polytime. Thus, the problem is NP.

2. Subset sum decision: Given a set of integers $S$ and an integer $T$, does there exist a subset $S^{\prime }\subseteq S$ such that ${\displaystyle {\sum }_{x\in S^{\prime }}x=T}$ ?

3. Reduction: Construct a set $S^{\prime }=S\cup \{p,q\}$ where $p=\sum S$ and $q=2T$, which sums to $2\sum S+2T$.

   Given an algorithm to partition $S^{\prime }$ into two subsets, $R$ and $\bar{R}$, they must be of equal sum $\sum S+T$. Each subset cannot contain both $p$ and $q$ due to $p+q>\sum S+T$; one subset $R$ must contain $p$, and then the rest of the integers in $R$ must sum to $T$. This solves subset sum problem.

4. Calculating $\sum S$ is $O(n)$, thus the reduction is in polytime. In conclusion, the partition decision problem is NP-complete.

P3: Subset sum problem

Definition.

Subset sum decision: Given a set of integers $S$ and an integer $T$, does there exist a subset $S^{\prime }\subseteq S$ such that ${\displaystyle {\sum }_{x\in S^{\prime }}x=T}$ ?

Proof by reduction from 3-SAT.

1. Certificate: Calculating ${\displaystyle {\sum }_{x\in S^{\prime }}x}$ is $O(n)$, so verification is in polytime. Therefore, the problem is NP.

2. 3-SAT: Given a 3-CNF formula of $M$ clauses, does there exist a set of values that makes the formula True?

3. Reduction: For each variable $x_i$, create two base-2 integers $A_i,B_i$, whose bits are:

   • $N$ variable-slots: only the $i$-th digit is marked 1, other digits are marked 0.
   • $M$ clause-slots: for each clause $C_j$:
     • If $x_i$ exists in the clause $C_j$, then $A_i$’s $N+j$ bit should be 1, otherwise 0.
     • If $\neg x_i$ exists in the clause $C_j$, then $B_i$’s $N+j$ bit should be 1, otherwise 0.

   For example, for a formula $(a\vee b\vee c)\wedge (\neg a\vee \neg b\vee c)$, we have 3 variables and 2 clauses, therefore 5 digits:

   • $A_1$: $10010$ (being the 1st variable; $a$ appearing in $C_1$)
   • $B_1$: $10001$ (being the 1st variable; $\neg a$ appearing in $C_2$)
   • $A_2$: $01010$ (being the 2nd variable; $b$ appearing in $C_1$)
   • $B_2$: $01001$ (being the 2nd variable; $\neg b$ appearing in $C_2$)
   • $A_3$: $00111$ (being the 3rd variable; $c$ appearing in $C_1$ and $C_2$)
   • $B_3$: $00100$ (being the 3rd variable; $\neg c$ not appearing at all)

   Let the subset sum $T=2^{N+M}-1$ and in the example, $11111$. By finding a satisfying subset, e.g., $\{A_1,B_2,B_3\}$, we have found the answer to the 3-SAT as well, since each variable-slot is satisfied exactly once, and each clause-slot is satisfied also exactly once.

4. The construction of the base-2 integers costs at least $O(N+M)$, which is in polytime. In conclusion, the subset sum problem is NP-complete.

#Algorithms