# NP-complete reduction: (grid-)Hamiltonian circuit

## Background

Hamiltonian circuit problem is a decision problem which asks whether a given graph has a Hamiltonian circuit, i.e. a cycle that visits every vertex exactly once. This problem is one of the well-known NP-complete problems.

It is also known that it remains so when restricted to grid graphs. Here, a grid graph is a graph defined by a set of vertices placed on 2D integer coordinates, where two vertices are connected by an edge if and only if they have Euclidean distance of 1.

For example, the following are an example of a grid graph and an example of a graph that is not a grid graph (if two vertices with distance 1 are not connected, it is not a grid graph):

Grid graph    Not
+-+       +-+
| |       |
+-+-+-+   +-+-+-+
| | |     |   |
+-+-+     +-+-+


NP-complete problems are reducible to each other, in the sense that an instance of problem A can be converted to that of problem B in polynomial time, preserving the answer (true or false).

## Challenge

Given a general undirected graph as input, convert it to a grid graph that has the same answer to the Hamiltonian circuit problem in polynomial time. Note that you cannot solve the problem on the input directly, unless P=NP is proven to be true.

A graph can be input and output in any reasonable format. Additionally, a list of coordinates of the grid graph is a valid output format.

Standard rules apply. The shortest code in bytes wins.

• Is it guaranteed that this is possible to achieve in polynomial time? Jun 30, 2021 at 8:07
• @DominicvanEssen Theoretically, yes. Practically, no one has done an explicit construction as far as I'm aware. Jun 30, 2021 at 8:36
• How many dimensions are you allowed? If the limit is 2, how can you even construct a grid graph for the graph (0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5) or the graph (0, 1), (0, 2), (0, 3), (0, 4), (0, 5)?
– Neil
Jun 30, 2021 at 10:31
• @Neil - this was what I was wondering initially (it's easy to think of a graph without an equivalent grid graph), but of course we're only being asked to get 'a grid graph that has the same answer', rather than to an equivalent grid graph. But without being able to calculate the answer in polynomial time, this does seem daunting to me at first sight... Jun 30, 2021 at 10:38
• @Neil The same question was asked in chat, and this is my answer. Jun 30, 2021 at 10:41