3
$\begingroup$

I had an idea for a way of representing DAGs, it's very easy to explain:

Each node in the DAG is given an array of n integers. If it is possible to traverse from A to B then each of B's integers must be greater than each of A's respective integers.

For example the graph:

A o - > o C
    \
     -> 
B o - > o D

Could be represented by:

A = [0,1]
B = [1,0]
C = [1,2]
D = [2,2]

I have a few questions:

  • Has such a representation been thought up before?
  • If no, would you help me to design an algorithm that generates the arrays of integers given a DAG?
$\endgroup$
15
$\begingroup$

[Revised.] I think that there has been a little confusion about what I was referring to in my original answer. I am revising it in order to better describe the result.

Note that your representation will only be capable of representing transitively-closed DAGs, i.e. partial orders; and this representation is a previously-studied one for partial orders. For instance, a paper by Mihalis Yannakakis shows that determining whether a partial order (equivalently, a transitively-closed digraph) has such a representation is NP-complete for n ≥ 3, but feasible if n ≤ 2.


Also, because the representation describes transitively closed DAGs, the body of research on the Transitive Closure problem is a reasonable place to look for related representations. My original response described a representation which, as it turned out, was strictly less general than the representation in terms of vectors. However, your representation has some similarities to the tree-cover representation of transitively closed DAGs (see Efficient management of transitive relationships in large data and knowledge bases: also described briefly in this article).

  • Without loss of generality, if the DAG has more than one 'source' (vertex with in-degree 0), add a virtual 'root' which can reach all of the sources. The entire DAG then has a spanning tree.

  • For each vertex, define an interval [ av , bv ] to each vertex v, in such a way that the interval at each node contains the intervals of all its descendants. (For instance, the upper bound bv for each v can be taken to be the post-fix order of the vertex in the tree; the lower bound av is the minimum of these post-fix values for the sub-tree.)

  • To represent directed edges which are not in the tree, each node keeps a list of the intervals of the different nodes which are reachable from it. (For any given sub-tree which is reachable from a given node, it suffices to record the interval belonging to the root of that sub-tree.)

Thus, the in-bound edges of each vertex is represented by the single interval [ av , bv ] , and its outbound edges are represented by a union of disjoint intervals which strictly contain the intervals of vertices that it can reach.

Some observations:

  1. The vector representation is related to the interval nesting condition by using higher dimensional "intervals". Without loss of generality, the length n of the array xv at each vertex is even (by buffering with a final dummy co-ordinate if needed). Let m = n/2. Partition the coefficients as $$ \mathbf x^v \;=\; [ \;a^v_1 \;,\; \ldots \;,\; a^v_m \;;\; c^v_1 \;,\; \ldots \;,\; c^v_m \;] $$ For each 1 ≤ j ≤ m , let $$ U_j = \left( \max_v \;\; a^v_j \right) + \left( \max_v \;\; c^v_j \right). $$ Then, we may define for each node an m-fold cartesian product of intervals, $$ I^v \;=\; [\;a^v_1\;,\; U_1-c^v_1 \;] \times \cdots \times [\;a^v_m\;,\; U_m-c^v_m \;]. $$ Two such "$m$-dimensional intervals" nest if and only if the corresponding vectors have the appropriate ordering relations. It is trivial to verify that the intervals nest only if the corresponding vectors are ordered; for the converse, we depend on none of the coefficients in the graph being larger than the corresponding bounds Uj .

  2. It is not clear to me whether the representation by vectors and by tree-covers are efficiently interconvertible; however it is easy to show that the case n = 2 corresponds exactly to the representation of directed trees in terms of tree-covers (i.e. the two representations are efficiently and reversibly inter-convertible, essentially by the technique I described above). Thus, the dimension may in some sense correspond to how tree-like the digraph is.

$\endgroup$
  • $\begingroup$ Niel, I don't know if you saw my answer: the key notion is the "dimension": there's a relatively simple argument that shows that the dimension of a lattice is at most its width, and indeed your example shows that this inequality can be made quite loose (2 vs n) $\endgroup$ – Suresh Venkat Apr 4 '11 at 15:26
  • $\begingroup$ @Suresh: it turns out that there is possibly more than one meaning of the phrase "chain decomposition". The literature on intersections of linear orders describe those orders as "chains"; but this is different from the vertex-disjoint decomposition into "chains" in the graph which I described. But never mind; if everyone assumed that I meant the former instead of the latter, I can revise my answer correspondingly. $\endgroup$ – Niel de Beaudrap Apr 4 '11 at 15:52
8
$\begingroup$

As Niel noted, your representation is transitively closed. If we go from a digraph to its transitive closure (which is a partial order) then your representation is used to define the dimension of a partial order.

Specifically, the dimension of a partial order corresponds to the minimum number of "coordinates" you need in your representation to correctly capture the ordering relationship among elements.

$\endgroup$
6
$\begingroup$

Has such a representation been thought up before?

For partial orders, yes. A lot of tableaux/sequent calculi for modal logics have used lists of integers to represent "possible worlds" and incorporate the relationships between worlds. It's an old technique (I think first going back to Fitting's work, I think in "Intuitionistic logic, model theory and forcing" or Proof methods for modal and intuitionistic logics).

$\endgroup$

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.