# Is there an efficient method to store large DAGs?

I have a DAG representing strict partial order where each node is an assignment of variables $V$ to their values $v$. Each arc $(u,w)$ represents a change in one variable value such that $u\succ w$.

So if I have $n$ binary variables, I will end up with $2^n$ nodes which is exponential to the size of variables $n$. is there any method to store such DAG efficiently?

• Why store anything? You can compute if there is an edge $(u,w)$ by using the same function that makes the edge that go between $u$ and $w$. Dec 18 '12 at 5:41
• @PratikDeoghare actually i'm trying to solve dominance task: given two nodes $n_1$ and $n_2$ which one is better $n_1\succ n_2$ or $n_2\succ n_1$. I can partially search the graph starting from $n_1$ for example. But this is hard problem in general. so I was looking for a method to index all the nodes and make it easier to answer the dominance task. Dec 18 '12 at 5:48
• @Seteropere I agree with Pratik. I did not understand what you mean by ".. which one is better ..". If I understand correctly, either $n_1 \prec n_2$ or $n_2 \prec n_1$ or neither dominates each other. You can check this by a linear traversal of the vectors of both $n_1$ and $n_2$. Did I miss something? Dec 18 '12 at 17:08
• @Paresh You got it. would you please elaborate more on *linear traversal of the vectors of both *. You mean checking outgoing paths from both $n_1$ and $n_2$ ? Dec 18 '12 at 19:24
• @Seteropere Say each point is a vector $\overrightarrow{v}$ of $m$ values (of any type). Say, you want to compare $n_1$ and $n_2$ having vectors $\overrightarrow{v_1}$ and $\overrightarrow{v_2}$ respectively. Then, for each of the $m$ values in $\overrightarrow{v_1}$ and $\overrightarrow{v_2}$, compare which dominates/is greater than the other. If all values of $\overrightarrow{v_1}$ dominate the corresponding values of $\overrightarrow{v_2}$, then $n_1$ dominates $n_2$, and vice-versa. If some values dominate, and some are dominated, then neither $n_1$ nor $n_2$ dominate each other. Dec 19 '12 at 16:27

Try constructing a reduced ordered binary decision diagram (ROBDD) as described here. The reducing algorithm removes redundant nodes, and reuses equal subtrees in the decision tree, such that every node is unique. The memory complexity of a ROBDD is $\mathcal O({2^n \over n})$ as proved here.