0
$\begingroup$

I was wondering if anyone knew of an algorithm that when given a directed graph will split it up into separate Hamiltonian paths. I don't really mind about nodes that can't be added to a path but as few paths as possible should be made to include the most nodes.

Any ideas would be greatly appreciated.

$\endgroup$
  • $\begingroup$ Assume that you are not looking for the brute force algorithm. Are you aware that finding one Hamiltonian path of a given directed graph is a NP-hard problem? $\endgroup$ – Apass.Jack Jul 21 at 5:45
  • $\begingroup$ Usually a Hamiltonian path is meant to cover nodes. If that is what you meant, then one Hamiltonian path should be enough, i.e., multiple Hamiltonian paths are out of the question. If you wanted them to cover all the edges, please clarify. $\endgroup$ – Apass.Jack Jul 21 at 5:49
  • $\begingroup$ @Apass.Jack in a directed graph it's not always possible to create a Hamilton path so it would have to then split it up into two or more smaller graphs. I don't need it to be perfect but was wondering if there is an existing algorithm that does it well enough $\endgroup$ – Swanny Jul 21 at 6:26
  • $\begingroup$ Thanks for your reply. Please add your clarification to the question. Comments are always secondary source as they are excluded from the summary and ignored by many search engines and people. The title should be something like "Decomposition of directed graphs into vertex-disjoint induced subgraphs with Hamiltonian paths". Remove "vertex-disjoint" if you do not forbid that. $\endgroup$ – Apass.Jack Jul 21 at 6:35
0
$\begingroup$

Finding an Hamilton path in directed (and un-directed) graphs, is an $NP$ complete problem. Thus, there is probably no efficient algorithm (polynomial) to split a given graph to several hamiltonian paths.

$\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.