Finding a Hamiltonian Cycle in a directed graph - graph problem

Question

$N$ towns are given, which we can get to by passing through the northern and southern gates. If you enter a town through a gate, you have to use another gate to leave the town. The merchant would like to plan his journey in such a way that starting from any town, he visits all towns exactly once and returns to the starting town.

The connection network of towns is given as a list of tuples $G$ (towns are numbered from $0$). The i-th tuple contains two lists: the first list contains the numbers of towns that can be reached from the i-th town via the i-th town's northern gate, the second one - similarly, only with the southern gate. It is guaranteed that we will be able to get to at least one city from each gate.

When you travel to a city, you have to go through this gate, from which we can get to the city you came from.

For example for $G=[([1],[2]),([2],[0]),([0],[1])]$ if we want to get from city $0$ to city $1$, we have to go through the north gate in city $0$ (because $1$ is in the first list in the tuple) and we have to go through the south gate in city $1$ (because the number of the city we came from - $0$, is in the second list in the tuple)

I need to find an algorithm that, given a list $G$, returns a list of the numbers of the cities visited consecutively by the merchant (or None if no such route is possible).

Example:

G = [ ([1], [2, 3, 4]),    
 ([0], [2, 5, 6]),        
 ([1, 5, 6], [0, 3, 4]),    
 ([0, 2, 4], [5, 7, 8]),    
 ([0, 2, 3], [6, 7, 9]),    
 ([1, 2, 6], [3, 7, 8]),    
 ([1, 2, 5], [4, 7, 9]),    
 ([4, 6, 9], [3, 5, 8]),    
 ([3, 5, 7], [9]),    
 ([4, 6, 7], [8]) ]

the result is the list [ 0, 1, 5, 7, 9, 8, 3, 2, 6, 4 ]

The first thing that popped into my head, because it is quite obvious, is that this is a Hamiltonian cycle problem (because we have to visit each vertex of the graph exactly once and return to the starting vertex). However, the condition related to gates indicates that we are dealing with a directed graph (at least that's what I think), which complicates things.

Would anyone have an idea how to solve this problem in a reasonable time (I know the Hamiltonian cycle problem is NP-complete, but suppose the number of vertices is not large)?

Answer 1

You can introduce a network $G_{new}$ such as follows:

For each vertex i (or town) in G introduce two vertices $i'$ (for north gate) and $i''$ (for south gate) which are connected to each other; i.e. There exist both arcs $i'i''$ and $i''i'$. Moreover, if we can move between $i$ and $j$ from northern gate of vertex $i$ then add $i'j'$ and $i'j''$ arcs and if we can move between $i$ and $j$ from southern gate of vertex $i$ then add $i''j'$ and $i''j''$ arcs.

Now, it is sufficient to introduce a Hamiltonian cycle on $G_{new}$, where for all vertices $i'$ and $i''$, we should traverse exactly one of the arcs $i'i''$ or $i''i'$; e.g. add the constraint $X_{i'i''}+X_{i''i'}=1$ to an optimization model of the Hamiltonian cycle problem.