Generation of All Path in a Directed Acyclic Graph - MathOverflow

Generation of All Path in a Directed Acyclic Graph

2012-08-23T15:43:26Z

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.

Answer by joro for Generation of All Path in a Directed Acyclic Graph

2012-08-23T17:00:40Z

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.

Answer by Rosh for Generation of All Path in a Directed Acyclic Graph

2012-10-24T00:59:37Z

My just published book , " A New Algorithm for Studying Routes in a Connected Graph', Kindle Edition, by Amazon. Com may be helpful in your problem. My new algorithm does not employ search, recursion or AI. It is based on combinatorial Analysis/Block Design. My algorithm produces all routes of length (PL) between the starting node, s and all other nodes. The number of such routes is simply Avg(Nc)^PL where Avg(Nc) is average degree of nodal connectivity. My software package (EcoNets) also selects routes (simple or cyclic) between any two nodes s and t. It can also select any routes with any set of route-attributes such as distance, link costs or reliabilities. A sample network (10n, 20s) took about 1 minute of my laptop and about 1 Gigabytes of RAM for all routes with PL <=10.