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.
Thanks in advance.
Best Answer
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).
To check if you are lucky, you can efficiently count the number of paths via powers of the adjacency matrix.
The open source software sage (available online at http://sagenb.org/) has a method "all_simple_paths()" that does exactly what you want.