I am working on a very large dataset of a single [DAG](http://en.wikipedia.org/wiki/Directed_acyclic_graph) whose vertices have a low branching factor. I need to generate all possible (simple) paths starting from the source and write them to a file.


My question is: what is [computational complexity](http://en.wikipedia.org/wiki/Computational_complexity_theory) class of this problem?


If this problem is [NP-Hard](http://en.wikipedia.org/wiki/NP-hard), is there any relatively space-efficient algorithm that can generate this exponential number of paths iteratively?


*Any references are extremely appreciated.*


Thanks in advance.



Generation of All Path in a Directed Acyclic Graph
The worst case is exponential in the number of nodes. Consider an [Ordered Binary Decision Diagram](https://en.wikipedia.org/wiki/Binary_decision_diagram) (OBDD) which is a DAG with outdegrees 2. Let it be on $n$ boolean variables and on $m$ nodes. Each assignment of the variables corresponds to a path to either True or False, so there are at least $2^n$ (simple) paths. Even if outputting a path is $O(1)$, you will have to do it $2^n$ times (not counting the inner paths).


To check if you are lucky, you can efficiently count the number of paths via powers of the [adjacency matrix](https://en.wikipedia.org/wiki/Adjacency_matrix).


The open source software [sage](http://sagemath.org) (available online at <http://sagenb.org/>)
has a method "all\_simple\_paths()" that does exactly what you want.


