Skip to content

Hamiltonian graphs

Given a directed graph \(G = (V, E)\), a Hamiltonian path is a path that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle.

Hamiltonian cycle search and decision problem

The Hamiltonian cycle decision problem consists in deciding whether a Hamiltonian path exists in the graph. It can either be a directed or undirected cycle. Both problems has been proven to be NP-complete (Karp, 1972) [1]. The search version of the problem consists in finding such a cycle.

The Hamiltonian cycle problem is a special case of the traveling salesperson decision problem where all the weights are equal to 1 and the cost \(|V|\).

Hamiltonian path search and decision problem

The Hamiltonian path decision problem consists in deciding whether a Hamiltonian path exists in the graph. It can either be a directed or undirected path. Both problems has been proven to be NP-complete [2]. The search version of the problem consists in finding such a path.

Finding a Hamiltonian path is equivalent to connect a new vertex to all the vertices in the graph and search for a Hamiltonian cycle in this new graph.

Hamiltonian path with fixed start and end points search and decision problem

The Hamiltonian path with fixed start and end decision problem consists in deciding, given two vertices \(v_s, v_e \in V\),whether a Hamiltonian path whose start is \(v_s\) and end \(v_e\) exists in the graph. It can either be a directed or undirected path. Both problems has been proven to be NP-complete [2]. The search version of the problem consists in finding such a path.

Finding a Hamiltonian path is equivalent to connect a new vertex \(v'\) to all the vertices in the graph and finding a feasible solution for the following 0-1 linear integer programming program:

For a directed path:

\[ \sum_{e \in \delta^+(u)} x_e = 1 \ \forall u \in V \cup \{v'\}\]
\[ \sum_{e \in \delta^-(u)} x_e = 1 \ \forall u \in V \cup \{v'\}\]
\[ x_{(v', v_s)} = 1 \]
\[ x_{(v_e, v')} = 1 \]

For an undirected path:

\[ \sum_{e \in \delta(u)} x_e = 2 \ \forall u \in V \cup \{v'\}\]
\[ x_{(v', v_s)} = 1 \]
\[ x_{(v_e, v')} = 1 \]

Traveling salesperson problem search decision problem

The traveling salesperson problem consists in deciding whether, given a cost \(C\), a Hamiltonian cycle with weigth smaller or equal than \(C\) exists in the graph. It can either be a directed or undirected cycle. Both problems are NP-complete (Proof 1).

If the graph is connected and \(\textbf{|V| > 2}\) (if it is not the case there is no such cycle), finding a Hamiltonian cycle is equivalent to find a feasible solution to this 0-1 integer linear program:

For a directed cycle:

\[ \sum_{e \in \delta^+(u)} x_e = 1 \ \forall u \in V \]
\[ \sum_{e \in \delta^-(u)} x_e = 1 \ \forall u \in V \]
\[ \sum_{e \in E} w_e x_e \leq C\]

For an undirected cycle:

\[ \sum_{e \in \delta(u)} x_e = 2 \ \forall u \in V \]
\[ \sum_{e \in E} w_e x_e \leq C\]

Proof 1

TSP is NP-hard since it is a generalization of the Hamiltonian cycle problem. However, it remains in NP as either the graph is not connected (polynomially checkable) and the problem has no solution, or the graph is connected in which case the problem is reducible to a 0-1 linear integer program.

[1] Karp, Richard M., “Reducibility Among Combinatorial Problems”. Complexity of Computer Computations, 1972: Plenum Press, 85-103.

[2] M.R. Garey and M.R. Johnson. Computers and Intractability. Freeman, New York, 1979.