Hamiltonian Path

Problem description

A Hamiltonian Path (or HP for short) in a directed graph G = (V,E), where V is the set of vertices and E is the set of edges, is a path in G such that every vertex v in V occurs exactly once in the path. The input of the HP problem is a directed graph. The goal is to find an HP in the graph.

Input format

A directed input graph is represented by the following predicates:

a. The vertices of the input graph are given by instances of "vtx" as follows:

vtx(name_1). vtx(name_2). ... vtx(name_n).

b. The edges of the graph are given by instances of "edge" as follows:

edge(name_1_1,name_1_2). edge(name_2_1,name_2_2). ... edge(name_m_1,name_m_2).

An instance edge(name_i_1,name_i_2) specifies that there is an edge from vertex name_i_1 to vertex name_i_2.

c. Finally, exactly one instance of "start" specifies the first vertex of the HP:

start(name).

For further illustration, compare the instances available at asparagus.

Output format

A solution is represented by means of a binary predicate "path" such that each instance of "path" corresponds to an edge. The edges in "path" must be the ones of some HP in the input graph.

Author: Lengning Liu, Miroslaw Truszczynski, and Martin Gebser
Affiliation: University of Kentucky and University of Potsdam