How to generate graphs with a Hamiltonian path?

Question

I need to create a graph generator for my next project. Generally algorithms are trying to find a Hamiltonian path in a graph. So I can create a graph generator, generate a graph, and then I can decide whether the graph has a Hamiltonian path or not. If not, I can regenerate the graph but this is not a cool way.

I want my generated graphs that always have a Hamiltonian path. My graph has two additional conditions:

• Vertices can only have 2, 3, or 4 edges.
• Possible number of vertices follow the sequence 6, 10, 15, 20, 25...n-5,n where n % 5 = 0.

How should I start, and how do I achieve this easily?

Answer 1

The simplest solution is the one suggested by Yuval Filmus. That is, take a simple path on $n$ vertices, and finish the construction after you have added some number of edges. Clearly, it is easy to enforce the maximum degree condition as well.

Alternatively, you could generate graphs whose structure guarantees the existence of a Hamiltonian path. For example, as shown by Tutte, every 4-connected planar graph has a Hamiltonian path (see e.g., Wikipedia for the statement). Then, a high-performance tool for generating planar graphs is plantri. My feeling is that this is unnecessarily complicated for your use case, but it gives you a possible another approach you might be interested in later on.

Answer 2

The solution suggested by Juho applies to any problem where you can generate an object that trivially has the property you're interested in and then modify it in a way that maintains that property:

• For the problem in the question, start with a path and randomly add edges obeying the degree conditions.

• To generate a graph with a $k$-clique, start with a $k$-clique, then add the rest of the vertices, then add edges at random.

• To generate $k$-colourable graphs, start with no edges, randomly choose the colour of each vertex and then randomly add edges between different coloured vertices.

• To generate satisfiable 3CNF formulas, start by picking a truth assignment for the variables and then add random clauses that have at least one true literal.

• To generate unsatisfiable 3CNF formulas, start with something simple and unsatisfiable and add random clauses to it.

If you don't care about the distribution of the instances you generate, these methods work fine. If you do care about the distribution, things get trickier. If you want a uniform or near-uniform distribution (i.e., each Hamiltonian graph on $5n$ vertices is generated with [roughly] equal probability), you should look into Fully Polynomial Almost Uniform Samplers (FPAUS). These typically use Markov chain Monte Carlo and the method for your problem would probably be to start with a path and then randomly add and remove the extra edges enough times that the process converges to the right distribution (you'd have to check this actuall works).

Another thing to be aware of is that instances generated in this way might be easy to solve if you knowsomething about how they were generated. For example, in the clique example I gave, if you just add each the non-clique edge independently with probability $p$ for some $p$, it's very likely that your clique is just the $k$ vertices of highest degree.

Answer 3

How about:

1. Start with a fully connected graph.
2. Choose a random permutation of the list of all nodes - this will be our guaranteed Hamiltonian cycle.
3. Delete an edge from the graph at random, as long as it is not
   • in our protected HC path
   • going to leave any vertex with too few edges.
4. Repeat step 3 until all your vertices have a degree in your required range.

To implement steps 3 and 4 above, you could shuffle the non-HC edges into a queue; then you pop edges off in turn and decide whether to drop or keep. You'd also better keep track of the number of edges for each node so that you know whether you can drop an edge and also when to stop altogether.