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.

Improve this question
$\endgroup$
4
  • 1
    $\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$
    – John L.
    Commented Jul 21, 2019 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$
    – John L.
    Commented Jul 21, 2019 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
    Commented Jul 21, 2019 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$
    – John L.
    Commented Jul 21, 2019 at 6:35

1 Answer 1

Reset to default
1
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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