# Generation of All Path in a Directed Acyclic Graph

I am working on a very large dataset of a single DAG 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 class of this problem?

If this problem is NP-Hard, is there any relatively space-efficient algorithm that can generate this exponential number of paths iteratively?

Any references are extremely appreciated.

• The worst case is exponential in the number of nodes. Consider a Binary Decision Diagram (BDD) 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 iterating a path is O(1), you will have to do it $2^n$ times (not counting the inner paths). You may be lucky with your specific case though. – joro Aug 23 '12 at 16:13
The worst case is exponential in the number of nodes. Consider an Ordered 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).