# Decomposition of a directed graph into Hamiltonian paths

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.

• 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? – John L. Jul 21 '19 at 5:45
• 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. – John L. Jul 21 '19 at 5:49
• @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 – Swanny Jul 21 '19 at 6:26
• 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. – John L. Jul 21 '19 at 6:35

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.