More generally relating on this...
I think that currently we have
1) Deterministic function to find the longest path of a graph.
2) "Usually fast" randomized function to find the longest path.
Is this true? And what about functions to find longest cycle or to check
if the graph is Hamiltonian? A function to list all Hamiltonian
paths/cycles?
Anyways, from 1 we can make a function to use for
is_hamiltonian(path=True), and with 2 we could have
is_hamiltonian(path=True, algorithm='randomized') or so.
Actually we have hamiltonian_cycle(algorithm='backtrack') that uses
randomized algorithm. It feels slightly odd -- to me "backtrack" sounds
like a deterministic function. And hamiltonian_path(algorithm='backtrack')
tries to find longest path by randomized algorithm, and returns what it
found -- i.e. not necessarily a Hamiltonian path.
I think it would be natural to have
is_hamiltonian(path=False, algorithm=None, certificate=False)
so that path=True would check if the graph is semi-Hamiltonian,
algorithm='randomized' would use the randomized algorithm which could give
false negatives, and certificate=True would give either (True, Cycle/Path)
or (False, None) as output.
But I am not an expert, so maybe graph theorists have something to say
about this.
--
Jori Mäntysalo
