NP-Completeness

$$NP$$-completeness is a property of some computational problems, which makes them amongst the hardest computational problems, and also at least as hard as each other.

Definition

A decision problem is a problem with a yes/no answer (or 0/1, true/false).

Polynomial time is a running time for an algorithm which is some polynomial multiplied by the size of the algorithm’s
inputs $$N$$, such as $$N$$, $$log\ N$$, $$N\ log\ N$$, $$N^2$$, or $$N^3$$, but not $$2^N$$ or $$N!$$.

A deterministic algorithm is one which, when it has to pursue several options, needs to pursue them one at a time.
A nondeterministic algorithm is one which, when it has to pursue several options, can pursue them simultaneously.
A nondeterministic algorithm is faster than a deterministic algorithm, but it is no more powerful in the sense of
being able to solve problems that a deterministic algorithm can’t.

The class $$P$$ is the class of decision problems that can be solved in polynomial time by a deterministic algorithm.
The class $$NP$$ is the class of decision problems that can be solved in polynomial time by a nondeterministic algorithm.
It follows from this that $$P$$ is a subset of $$NP$$.

A polynomial reduction is an polynomial time algorithm that can transform an instance of a problem $$A$$
(decision or otherwise) into an instance of another problem $$B$$, such that the solution is preserved, i.e., for every
instance of $$A$$, if the solution of $$A$$ is yes, then the instance of $$B$$ produced by the polynomial transformation will also
be yes, and the same for no, or any other value.

A problem (decision or otherwise) is $$NP$$-hard if every problem in $$NP$$ can be reduced to it by a polynomial reduction.
So $$NP$$-hard can be read as “at least as hard as $$NP$$“.
A problem is $$NP$$-complete if it is $$NP$$-hard and it is in $$NP$$.

So a problem is $$NP$$-hard but not $$NP$$-complete if it isn’t in $$NP$$.
There are two two reasons for this:
1. It isn’t a decision problem, which means it isn’t in $$NP$$
2. It isn’t decidable, e.g., the Turing machine Halting Problem is $$NP$$-hard, but not in $$NP$$ because the definition of $$NP$$
requires there is an algorithm, but by definition no algorithm exists for undecidable problems.

Since every problem in $$NP$$ can be reduced to any $$NP$$-complete problem, but the converse is not true, the $$NP$$-complete
problems can be seen as the hardest problems in $$NP$$.

Most scientists believe that there is no polynomial time algorithm that can solve an $$NP$$-hard problem.
This means that there are problems in $$NP$$ that are not in $$P$$, so $$P \neq NP$$.
This is the $$P-NP$$ Problem.

Karp’s 21 Problems

Richard Karp’s 1972 paper “Reducibility Among Combinatorial Problems” demonstrated the $$NP$$-completeness of 20 problems by reducing the known $$NP$$-complete problem SATISFIABILITY directly or indirectly to them as in the following diagram:

Problem definitions

SATISFIABILITY

INPUT: Clauses $$C_1, C_2, \dots, C_p$$

PROPERTY: The conjunction of the given clauses is satisfiable;
i.e., there is a set $$S \subseteq \{x_1, x_2, \dots, x_n;\overline{x_1}, \overline{x_2}, \dots, \overline{x_n}\}$$ such
that
a) $$S$$ does not contain a complementary pair of literals and
b) $$S \cap C_k \neq \emptyset, k = 1, 2, \dots, p$$

2. 0-1 INTEGER PROGRAMMING

INPUT: Integer matrix $$C$$ and integer vector $$d$$

PROPERTY: There exists a $$0-1$$ vector $$x$$ such that $$C_x$$ = $$d$$.

3. CLIQUE

INPUT: Graph $$G$$, positive integer $$k$$

PROPERTY: $$G$$ has a set of $$k$$ mutually adjacent nodes.

4. SET PACKING

INPUT: Family of sets $$\{S_j\}$$, positive integer $$\ell$$

PROPERTY: $$\{S_j\}$$ contains $$\ell$$ mutually disjoint sets.

5. NODE COVER

INPUT: Graph $$G^\prime$$, positive integer $$\ell$$

PROPERTY: There is a set $$R \subseteq N^\prime$$ such that $$|R| \le \ell$$ and
every arc is incident with some node in $$R$$.

6. SET COVERING

INPUT: Finite family of finite sets $$\{S_j\}$$

PROPERTY: There is a subfamily $$\{T_h\} \subseteq \{S_j\}$$ containing $$\le k$$
sets such that $$\bigcup T_h = \bigcup S_j$$.

7. FEEDBACK NODE SET

INPUT: Digraph $$H$$, positive integer $$k$$

PROPERTY: There is a set $$R \subseteq V$$ such that every (directed)
cycle of $$H$$ contains a node in $$R$$.

8. FEEDBACK ARC SET

INPUT: Digraph $$H$$, positive integer $$k$$

PROPERTY: There is a set $$S \subseteq E$$ such that every (directed)
cycle of $$H$$ contains an arc in $$S$$.

9. DIRECTED HAMILTON CIRCUIT

INPUT: Digraph $$H$$

PROPERTY: $$H$$ has a directed cycle which includes each node exactly once.

10. UNDIRECTED HAMILTON CIRCUIT

INPUT: Graph $$G$$

PROPERTY: $$G$$ has a cycle which includes each node exactly once.

11. SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE

INPUT: Clauses $$D_1, D_2, \ldots, D_r$$, each consisting of at most 3
literals from the set $$\{u_1, u_2, \ldots, u_m\} \cup \{\overline{u_1}, \overline{u_2}, \ldots, \overline{u_m}\}$$

PROPERTY: The set {$$D_1, D_2, \ldots, D_r$$} is satisfiable.

12. CHROMATIC NUMBER

INPUT: Graph $$G$$, positive integer $$k$$

PROPERTY: There is a function $$\phi: N \to \mathbb{Z_k}$$ such that, if $$u$$
and $$v$$ are adjacent, then $$\phi(u) \ne \phi(v)$$.

13. CLIQUE COVER

INPUT: Graph $$G$$, positive integer $$\ell$$

PROPERTY: $$N^\prime$$ is the union of $$\ell$$ or fewer cliques.

14. EXACT COVER

INPUT: Family $$\{S_j\}$$ of subsets of a set $$\{u_i, i = 1, 2, \ldots, t\}$$

PROPERTY: There is a subfamily $$\{T_h\} \subseteq \{S_j\}$$ such that the
sets $$T_h$$ are disjoint and $$\bigcup T_h = \bigcup S_j = \{u_i, i = 1, 2, \ldots, t\}$$.

15. HITTING SET

INPUT: Family $$\{U_i\}$$ of subsets of $$\{S_j, j = 1, 2, \ldots, r\}$$

PROPERTY: There is a set $$W$$ such that, for each $$i$$, $$|W \cap U_i| = 1$$.

16. STEINER TREE

INPUT: Graph $$G$$, $$R \subseteq N$$, weighting function $$w: A \to \mathbb{Z}$$,
positive integer k

PROPERTY: $$G$$ has a subtree of weight $$\leq k$$ containing the set of nodes in $$R$$.

17. 3-DIMENSIONAL MATCHING

INPUT: Set $$U \subseteq T \times T \times T$$, where $$T$$ is a finite set

PROPERTY: There is a set $$W \subseteq U$$ such that $$|W| = |T|$$ and
no two elements of $$W$$ agree in any coordinate.

18. KNAPSACK

INPUT: $$(a_1, a_2, \ldots, a_r, b) \in \mathbb{Z}^{n+1}$$

PROPERTY: $$\sum a_j x_j = b$$ has a $$0-1$$ solution.

19. JOB SEQUENCING

INPUT:
“execution time vector” $$(T_1, \ldots, T_P) \in \mathbb{Z}^P$$
“deadline vector” $$(D_1, \ldots, D_P) \in \mathbb{Z}^P$$
“penalty vector” $$(P_1, \ldots, P_P) \in \mathbb{Z}^P$$
positive integer $$k$$

PROPERTY: There is a permutation $$\pi$$ of $$\{1, 2, \ldots, P$$} such that

$$\left( \sum_{j=1}^P [\text{if } T_{\pi(1)} + \dots + T_{\pi(j)} \gt D_{\pi(j)} \text{ then } P_{\pi(j)} \text{ else } 0]\right) \le k .$$

20. PARTITION

INPUT: $$(c_1, c_2, \ldots, c_s) \in \mathbb{Z}^S$$

PROPERTY: There is a set $$I \subseteq \{1, 2, \ldots, s\}$$ such that

$$\sum_{h \in I} c_h = \sum_{h \notin I} c_h$$

21. MAX CUT

INPUT: graph $$G$$, weighting function $$w: A \to \mathbb{Z}$$, positive
integer $$W$$

PROPERTY: There is a set $$S \subseteq N$$ such that

$$\sum_{\{u, v\} \in A, u \in S v \notin S} w(\{u, v\}) \ge W.$$

Reductions

SATISIFIABILITY $$\propto$$ 0,1 INTEGER PROGRAMMING

$$c_{ij} = \begin{cases} 1 & if\; x_j \in C_i\quad i=1, 2, \dots, p \\ -1 & if\; \overline{x_j} \in C_i\quad i=1, 2, \dots, n \\ 0 & otherwise\; \end{cases}$$
The vector $$b$$ is dimension $$p$$ with:
$$b_i$$ = 1 – (the number of complemented variables in $$C_i$$),
$$i = 1, 2, \ldots, p$$.

SATISFIABILITY $$\propto$$ CLIQUE

$$N = \{\langle \sigma, i\rangle | \sigma$$ is a literal and occurs in $$C_i\}$$
$$A = \{\{\langle \sigma, i\rangle, \langle\delta, j\rangle\} | i \neq j$$ and $$\sigma \neq \overline{\delta}\}$$
$$k = p$$, the number of clauses

CLIQUE $$\propto$$ SET PACKING

Assume $$N = \{1, 2, \ldots, n\}$$.
The elements of the sets $$S_1, S_2, \ldots, S_n$$ are those two-element sets of nodes $$\{i, j\}$$ not in $$A$$.
$$S_i = \{\{i, j\}| \{i, j\} \notin A\}, i = 1, 2, \ldots, n$$.
$$\ell = k$$.

CLIQUE $$\propto$$ NODE COVER

$$G^\prime$$ is the complement of $$G$$.
$$\ell = |N| – k$$.

NODE COVER $$\propto$$ SET COVERING

Assume $$N^\prime = \{0, 1, \ldots, n\}$$.
The elements are the arcs of $$G^\prime$$.
$$S_j$$ is the set of arcs incident with node $$j$$.
$$k = \ell$$.

NODE COVER $$\propto$$ FEEDBACK NODE SET

$$V = N^\prime$$.
$$E = \{\langle u, v\rangle | \{u,v\} \in A^\prime\}$$.
$$k = \ell$$.

NODE COVER $$\propto$$ FEEDBACK ARC SET

$$V = N^\prime \times \{0, 1\}$$.
$$E = \{\langle \langle u, 0 \rangle, \langle u, 1 \rangle \rangle| u \in N^\prime\} \cup \{\langle \langle u, 1\rangle, \langle v, 0\rangle\rangle| \{u, v\} \in A^\prime\}$$.
$$k = \ell$$.

NODE COVER $$\propto$$ DIRECTED HAMILTONIAN CIRCUIT

Without loss of generality assume $$A^\prime = Z_m$$.
$$V = \{a_1, a_2, \dots, a_\ell\} \cup \{\langle u, i, \alpha \rangle\ | u \in N^\prime$$ is incident with $$i \in A^\prime$$ and $$\alpha \in \{0, 1\}\}$$
$$E = \{\langle \langle u, i, 0 \rangle, \langle u, i, 1 \rangle, \rangle | \langle u, i, 0 \rangle \in V\}$$
$$\;\cup\;\{\langle \langle u, i, \alpha \rangle, \langle v, i, \alpha \rangle \rangle | i \in A^\prime, u$$ and $$v$$ are incident with $$i$$, $$\alpha \in \{0, 1\}\}$$
$$\;\cup\;\{\langle \langle u, i, 1 \rangle, \langle u, j, 0 \rangle \rangle | u$$ is incident with $$i$$ and $$j$$ and $$!\exists h, i \lt h \lt j,$$ such that $$u$$ is incident with $$h\}$$
$$\;\cup\;\{\langle \langle u, i, 1 \rangle, a_f \rangle | 1 \leq f \leq \ell$$ and $$!\exists h \gt i$$ such that $$u$$ is incident with $$h\}$$
$$\;\cup\;\{\langle a_f,\langle u, i, 0 \rangle \rangle | 1 \leq f \leq \ell$$ and $$!\exists h \lt i$$ such that $$u$$ is incident with $$h\}$$

DIRECTED HAMILTONIAN CIRCUIT $$\propto$$ UNDIRECTED HAMILTONIAN CIRCUIT

$$N = V \times \{0, 1, 2\}$$
$$A = \{\{\langle u, 0 \rangle, \langle u, 1\}, \{\langle u, 1 \rangle, \langle u, 2 \rangle\}| u \in V\}$$
$$\; \cup \{\{\langle u, 2 \rangle, \langle v, 0 \rangle\} | \langle u, v \rangle \in E\}$$

SATISFIABILITY $$\propto$$ SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE

Replace a clause $$\sigma_1 \cup \sigma_2 \cup \ldots \cup \sigma_m$$, where the $$\sigma_i$$ are literals and $$m \gt$$ 3, by
$$(\sigma_1 \cup \sigma_2 \cup u_1)(\sigma_3 \cup \ldots \cup \sigma_m \cup \overline{u_1})(\overline{\sigma_3} \cup u_1) \ldots (\overline{\sigma_m} \cup u_1)$$,
where $$u_1$$ is a new variable.
Repeat this transformation until no clause has more than three literals.

SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE $$\propto$$ CHROMATIC NUMBER

Assume without loss of generality that $$m \ge 4$$.
$$N = \{u_1, u_2, \ldots, u_m\} \cup \{\overline{u1}, \overline{u2}, \ldots, \overline{um}\} \cup {v1, v2, \ldots, v_m}$$
$$\;\cup \{D_1, D_2, \dots, D_r\}$$
$$A = \{\{u_i, \overline{ui}\}| i = 1, 2, \ldots, n\} \cup \{\{v_i, v_j\} | i \neq j\} \cup \{\{v_i, x_j\}| i != j\} \cup \{\{v_i, \overline{x_j}\}| i \neq j\}$$
$$\;\cup \{\{u_i, D_f\} | u_i \notin D_f\} \cup \{\{\overline{u_i}, D_f\}| \overline{u_i} \in D_f\}$$
$$k = r + 1$$

CHROMATIC NUMBER $$\propto$$ CLIQUE COVER

$$G^\prime$$ is the complement of $$G$$
$$\ell = k$$

CHROMATIC NUMBER $$\propto$$ EXACT COVER

The set of elements is
$$N \cup A \cup \{ \langle u, e, f\rangle | u$$ is incident with $$e$$ and $$1 \leq f \leq k\}$$.
The sets $$S_j$$ are the following:
for each $$f, 1 \leq f \leq k$$, and each $$u \in N$$,
$$\quad\{u\} \cup \{\langle u, e, f \rangle | e$$ is incident with $$u\}$$;
for each $$e \in A$$ and each pair $$f_1, f_2$$ such that
$$\quad 1 \leq f_1 \leq k, 1 \leq f_2 \leq k$$ and $$f_1 \neq f_2$$
$$\quad\{e\} \cup \{\langle u, e, f \rangle, f \neq f_1\} \cup \{\langle v, e, g \rangle | g \neq f_2\}$$,
where $$u$$ and $$v$$ are the two nodes incident with $$e$$.

EXACT COVER $$\propto$$ HITTING SET

The hitting set problem has sets $$U_i$$ and elements $$s_j$$ such that
$$s_j \in U_i \iff u_i \in S_j$$.

EXACT COVER $$\propto$$ STEINER TREE

$$N = \{n_0\} \cup \{S_j\} \cup \{u_1\}$$
$$R = \{n_0\} \cup \{u_i\}$$
$$A = \{\{n_0, S_j\}\} \cup \{\{S_j, u_i\}| u_i \in S_j\}$$
$$w(\{n_0, S_j\}) = |S_j|$$
$$w(\{S_j, u_i\}) = 0$$
$$k = |\{u_i\}|$$.

EXACT COVER $$\propto$$ 3-DIMENSIONAL MATCHING

Without loss of generality, assume $$|S_j| \geq 2$$ for each $$j$$.
Let $$T = \{\langle i, j \rangle | u_i \in S_j\}$$.
Let $$\alpha$$ be an arbitrary one-one function from $$\{u_i\}$$ into $$T$$.
Let $$pi: T \to T$$ be a permutation such that,
for each fixed $$j, \{\langle i, j\rangle | u_i \in S_j\}$$ is a cycle of $$\pi$$.
$$U = \{\langle \alpha(u_i), \langle i, j\rangle , \langle i, j\rangle \rangle | \langle i, j\rangle \in T\}$$
$$\quad\cup \langle \beta, \sigma, \pi(\sigma)\rangle | \text{for all } i, \beta \ne \alpha(u_i)\}$$.

EXACT COVER $$\propto$$ KNAPSACK

Let $$d = |\{S_j\}|+1.$$
Let $$\epsilon_ji = \begin{cases} 1 & if\; u_i \in S_j \\ 0 & if\; u_i \notin S_j \end{cases}$$
Let $$r = |\{S_j\}|, a_j = \sum \epsilon_{ji}d^{i-1}\;and\;b = \frac{d^t-1}{d-1}.$$

KNAPSACK $$\propto$$ SEQUENCING

$$p = r, T_i = P_i = a_i, D_i = b$$.

KNAPSACK $$\propto$$ PARTITION

$$s = r + 2$$
$$c_i = a_i i = 1, 2, \ldots r$$
$$c_{r+1} = b + 1$$
$$c_{r+2} = (\sum_{i = 1}^r a_i) + 1 – b$$

PARTITION $$\propto$$ MAX CUT

$$N = \{1, 2, \dots, s\}$$
$$A = \{\{i, j\} | i \in N, j \in N, i \ne j\}$$
$$w(\{i, j\}) = c_i \cdot c_j$$
$$W = [\frac{1}{4} \sum c_i^2]$$