• Table of Contents

Easy and Hard Problem

The traveling salesman problem, Hamiltonian cycle problem, longest path problem, and many other important computational problems have been shown to be NP-complete.

• This means that they are among the hardest problems in computer science, and it is unlikely that there is an efficient algorithm that can solve them in polynomial time.
• However, by using reduction, we can show that if we can solve an NP-complete problem in polynomial time, we can solve any problem in NP in polynomial time.

This is the basis for many algorithms that are used to solve these problems in practice.

Traveling Salesman Problem

According to the definition below, TSP is a search problem. This is because, when the order of vertices is given, determining whether the cost is less than $b$ and visiting all vertices can be solved within polynomial time proportional to the length of the vertices.

Figure 7.1 Definition of TSP.

An easy version of the TSP is the Minimum Spanning Tree Problem.

Figure 7.2 Easy version of TSP.

The difference is that MST looks for a tree while TSP looks for a path. The problem is finding the shortest simple cycle in the graph.

• Only decision problems can be NP-hard or NP-complete — these are problems for which the answer is either Yes or No.
• The TSP can defined as a decision problem to guarantee that a candidate solution can be efficiently checked for correctness.

The decision problem form is:

Given a graph $G=(V,E)$ and integer $b$, does the graph contain a simple cycle that passes through all vertices and has length $\leq b$?

• Example TSP Decision Form