5
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.