4
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – joro
    Commented Aug 23, 2012 at 16:13

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Y.H.
    Commented Aug 23, 2012 at 17:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .