Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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
add comment

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks for the OBDD example, I think there is no way to solve this problem but falling back to a naive brute-force attack since the enumeration of all possible paths is a goal not a side-effect. Considering a space-efficient algorithm I can think of an implementation where bit-vectors are used to represent paths for example. I will take a look at sage's method, thanks a lot. –  HJosef Aug 23 '12 at 17:49
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.