## Proving the set-covering problem is NP-complete (using reduction from the vertex cover problem)

In this post, we will prove that the decision version of the set-covering problem is NP-complete, using a reduction from the vertex covering problem (which is NP-complete). This is Exercise 35.3-2 in CLRS3.

We will follow the template given in an earlier post.

## Problem Statement

We seek to answer whether a set cover $$\mathcal{C}$$ exists for $$X$$ (the set containing the elements to be covered), containing a maximum of $$k$$ sets.

## How to show a problem is NP-complete

This is the first post in a series of posts where I will attempt to give visual, easy to understand, proofs of NP-completeness for a selection of decision problems. I created these while studying them back in college. Hopefully, they’ll be helpful for someone.

In this post, I will give a “template” which can be used (and will be used for the proofs I post). [Read More]

## Proving 0-1 integer programming is NP-complete (using reduction from 3-CNF-SAT)

In this post, we will prove that 0-1 integer programming is NP-complete using a reduction from 3-CNF-SAT (which is NP-complete).

We will follow the template given in an earlier post.

## Problem Statement

The decision problem for 0-1 integer programming is formulated as follows:

Given an integer $$m \times n$$ matrix $$A$$ and an integer $$m$$-vector $$b$$, determine whether there exists an integer $$n$$-vector $$x$$ with elements in $$\{0, 1\}$$, such that:

$Ax \le b$ [Read More]

## Proving set-partition problem is NP-complete (using reduction from subset sum)

In this post, we will prove that the set-partition problem is NP-complete using a reduction from the subset sum problem (which is NP-complete). This is also happens to be Exercise 34.5-5 in CLRS3.

We will follow the template given in an earlier post.

## Problem statement

Given a set $$S$$ of numbers, determine whether $$S$$ can be partitioned into $$A$$ and $$\overline{A} = S - A$$, such that: $\sum_{x \in A} x = \sum_{x \in \overline{A}} x$ [Read More]