Digraphs icon indicating copy to clipboard operation
Digraphs copied to clipboard

Implement a function `HamiltonianPath` that can return a path that is not necessarily a cycle

Open wilfwilson opened this issue 6 months ago • 1 comments

This follows on from #545, in which @TomGoertzen noticed that the HamiltonianPath function from Digraphs versions 0.x and 1.x only looks for and returns Hamiltonian cycles, even though the more general notion of a Hamiltonian path that is not necessarily a cycle does exist (see e.g. https://en.wikipedia.org/wiki/Hamiltonian_path).

I'm renaming HamiltonianPath to HamiltonianCycle in #824 for Digraphs version 2.0, but it would be nice if we could actually have a function HamiltonianPath that would (also) work for digraphs that don't necessarily a Hamiltonian cycle, such as the chain digraph.

It would have this behaviour:

gap> HamiltonianPath(ChainDigraph(3));
[ 1, 2, 3 ]
gap> HamiltonianCycle(ChainDigraph(3));
fail
gap> HamiltonianPath(CycleDigraph(3));
[ 1, 2, 3 ]
gap> HamiltonianCycle(CycleDigraph(3));
[ 1, 2, 3 ]

It could work just like HamiltonianCycle does in #824, except that the line corresponding to: https://github.com/digraphs/Digraphs/blob/5cf1c49149a0ca1eecdc4f68802040dcaf241d6b/gap/attr.gi#L2279 would look for a monomorphism from the chain digraph on the relevant number of vertices, rather than the cycle digraph.

Actually, in the case that the number of vertices is too big for DigraphMonomorphism, we need to do something a bit different than what HamiltonianCycle does (because it's easier to search through all cycles than all paths).

Could be a nice task for an enthusiastic student.

wilfwilson avatar Sep 10 '25 17:09 wilfwilson

I'll start working on this!

ap4108735 avatar Nov 05 '25 14:11 ap4108735