2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 4
    $\begingroup$ 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$. $\endgroup$ – Pratik Deoghare Dec 18 '12 at 5:41
  • $\begingroup$ @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. $\endgroup$ – seteropere Dec 18 '12 at 5:48
  • 1
    $\begingroup$ @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? $\endgroup$ – Paresh Dec 18 '12 at 17:08
  • $\begingroup$ @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$ ? $\endgroup$ – seteropere Dec 18 '12 at 19:24
  • $\begingroup$ @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. $\endgroup$ – Paresh Dec 19 '12 at 16:27
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank Simon. does it preserve the arcs? i.e. the reduced diagram will have same set of arcs as the original? $\endgroup$ – seteropere Dec 18 '12 at 19:35
  • 1
    $\begingroup$ Redundant arcs will be removed, i.e if the result of assigning 0 leads to an equal node as assigning 1. Any other arc is preserved. $\endgroup$ – Simon S Dec 18 '12 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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