Since Hamiltonian Cycle Problem is an NP-complete problem, it is at least as difficult as any other NP problem. Hence, instances of other NP problems can, in polynomial time, be converted into equivalent instances of HCP, and a valid Hamiltonian cycle in the resultant instance can, again in polynomial time, be converted into a valid solution of the initial problem. If the resultant instance of HCP is non-Hamiltonian then the initial instance has no solution either.
Problems converted in this way are often relatively difficult instances of HCP by comparison to size. However, the underlying difficulty of the initial instance is, in some sense, retained as well.
On this page we include source code (in Java) for converting some NP problems to HCP, and also for interpreting found Hamiltonian cycles in the context of the initial problems. We also include a few examples for each problem.
Boolean Satisfiability (SAT) is the problem of determining whether a set of boolean variables can be assigned values of TRUE or FALSE so that a given boolean expression evaluates to TRUE. Any such expression can be written in conjunctive normal form, that is, as a sequence of individual clauses only containing OR and NOT operators, and with each entry in the sequence joined by AND operators.
The Chromatic Number problem requests the minimum number of colours required to colour the vertices of a given graph so that no edge has endpoints of the same colour. The decision form of the problem asks whether such a vertex colouring is possible for a given number of colours k.
The generalised Instant Insanity problem asks, given n cubes where each face is coloured from a choice of n colours, can the cubes be arranged in a line and oriented in such a way that the four long faces each display all n colours.
The Queens problem asks, for a chessboard of size n x n, how should n queens be placed to ensure that no queen can take any other queen in a single move. This problem is known to have solutions for all n > 3.
The Set Splitting problem asks, for a given finite universe set U, and a family F of subsets of U, does there exist a partition of U into two disjoint non-empty subsets V and W such that each entry of F contains at least one element from both V and W.