12.8. A Brief Survey of Some Other NP-Complete Problems

This page lists some known NP-complete problem (and some related problems that are in P) without any proofs.

Hamilton cycle

---

A cycle in an indirected graph is a sequence of vertices v₀, v₁, …, v_n where

1. v₀ = v_n.
2. {v_i, v_i+1} is an edge for i = 0, …, n−1.

The length of cycle v₀, v₁, …, v_n is n.

A simple cycle is a cycle that does not contain any vertex more than once, except for the requirement that the first and last vertices are the same.

A Hamilton cycle in an undirected graph is a simple cycle that contains every vertex.

The Hamilton Cycle problem is:

Input. An undirected graph G.

Question. Does G have a Hamilton cycle?

Euler Cycle

---

An Euler cycle in an undirected graph is a cycle that uses each edge exactly once.

Euler cycles sound similar to Hamilton cycles, but they are actually very different.

So it is easy to see whether a graph has an Euler cycle!

Hamilton Path and Euler Path

---

Related problems are concerned with finding paths instead of cycles. We just remove the requirement that the path begin and end on the same vertices.

The problem of recognizing a graph that has a Hamilton path is NP-complete.

The problem of recognizing a graph that has an Euler path is in P. (Just check that the graph has exactly two vertices of odd degree. They are the start and end vertex of an Euler path.)

The Traveling Salesman problem

---

The idea of the Traveling Salesman problem is that a salesman wants to visit each town in his area, and he wants to travel the shortest total distance to do it. He starts at his home town and must return to his home town.

Suppose there are n towns. The input contains an n×n matrix D = [d_{i, j}] of distances, where d_{i, j} is the distance from town i to town j.

Normally, the distance matrix is required to be symmetric, so d_{i, j} = d_{j, i}. (That restriction does not affect how hard the problem is.)

The input also contains a desired total distance K.

The question is whether it is possible for a salesman visit all of the towns traveling a total distance of no more that K. Traveling from town i to town j costs distance d_{i, j}.

Traveling Salesman problem with triangle inequality

The Traveling Salesman problem does not require the distance matrix to be sensible.

For example, according to the matrix, it might be 10 kilometers from town 1 to town 2, and 10 kilometers from town 2 to town 3, but 1000 kilometers from town 1 to town 3.

The definition of the problem requires the salesman to travel 1000 kilometers to get from town 1 to town 3.

But suppose that we impose some sensibility onto the distances. The triangle inequality states that

for all i, j and k, d_{i, k} ≤ d_{i, j} + d_{j, k}.

Graph coloring

---

You color a graph by assigning each vertex a color from a given palette. The coloring must be chosen so that no two adjacent vertices have the same color.

The Graph Coloring problem is as follows.

Input. An undirected graph G and a positive integer K.

Question. Is it possible to color G using no more than K colors?

K-coloring

There are some variations on Graph Coloring. One is to fix K, so that it is no longer part of the input.

For example, the 3-Coloring problem is to determine whether a graph can be colored with 3 colors.

Coloring planar graphs

Another variation is to restrict the graph to be planar. A planar graph is one that can be drawn on a planar surface without any edges crossing.

The latter result is due to the 4-Color Theorem: every planar graph can be colored using 4 colors.

So we have a curious situation where coloring a planar graph is easy for 2 colors and 4 colors, but NP-complete for 3 colors.

The Partition problem

---

The Partition problem is a restriction of the Subset Sum problem.

Input. A list x₁, …, x_n of positive integers.

Question. Does there exist an index set I so that ∑_{j ∈ I} x_j = ∑_{j ∉ I} x_j?

Equivalently, the problem is to determine whether there is a sublist of x₁, … x_n that adds up to exactly half the sum x₁ + … + x_n