4
$\begingroup$

Fix a set $V$ of cardinality $n$. I'm trying to determine the number of possible DAGs (directed acyclic graphs) whose vertex set is $V$ with a longest path containing $k$ nodes, which I will write as $D^n_k$.

So far, I have

$$ D^n_k = {n \choose k} (\ldots) $$

The $n \choose k$ is required because we have to choose the vertices which form the longest path. I also know that the part in the parentheses needs to give the number of possible subgraphs of order $n - k$ which don't extend the path to more than $k$ vertices, but I don't know how to even describe this. Although I am after a closed form, a recurrence, or help in obtaining one, would be very helpful for me.

$\endgroup$
5
  • $\begingroup$ Are you interested in all DAGs or all DAGs up to isomorphism? $\endgroup$
    – eepperly16
    Dec 21 '17 at 2:04
  • $\begingroup$ I'm not sure. My DAG represents the dependencies of a program's instructions, and the intended set of vertices are a consecutive subset of the natural numbers starting from 0, which are basically the instructions in the order they appear in the program, and the edges are the dependencies between them. $\endgroup$
    – Koz Ross
    Dec 21 '17 at 2:13
  • $\begingroup$ @eepperly16 All DAGs. Please ignore my comment above - I did some thinking and understand I need all DAGs. $\endgroup$
    – Koz Ross
    Dec 22 '17 at 0:35
  • 1
    $\begingroup$ This seems like a very complicated problem and I’m not sure a closed form solution exists. $\endgroup$
    – eepperly16
    Dec 22 '17 at 0:49
  • $\begingroup$ For that application, are you sure you want DAGs rather than posets (transitive DAGs)? I mean: do you care about whether B depends directly on C, given that B depends on C indirectly? $\endgroup$
    – Dap
    Dec 27 '17 at 8:47
1
+50
$\begingroup$

(Too long for a comment, not a full answer) If we forget about the $k$ parameter and just look at the number of DAGs on $n$ labeled nodes then the total number of DAGs is given by the recurrence $$ D_n = \sum_{k=1}^n(-1)^{k-1}\dbinom{n}k2^{k(n-k)}D_{n-k}.$$ If the nodes are not labeled, just divide by $n!$. This is also the OEIS sequence A003024. The first few numbers are $$1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, 4175098976430598143, 31603459396418917607425$$ so $D_n$ grows very quickly. As a very crude bound, if we only take the first term in the sum we get $$ D_n \approx 2^nD_{n-1}$$ so $D_n \approx 2^{n^2}$ (It grows even faster than this).

If we make the bad assumption that all longest path lengths are equally likely, then the number of DAGs on $n$ labeled nodes with longest path having length $k$ is roughly $\frac{D_n}k.$ However, some longest paths are much more likely than others. More precisely,

If we randomly pick a DAG out of all possible $D_n$ DAGs, what is the expected length of the longest path ?

If we forget about labels, and also orientation of the edges, it is plausible to believe that the question is roughly the same as asking

If we randomly pick a tree out of all possible trees with $n$ vertices, what is the height of the tree?

This question has been answered here and the expected height is roughly $O(\sqrt{n}).$ Thus, for $k$ far away from $O(\sqrt{n})$, there might be much less than $D_n/n$ possibilities.

$\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.