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