Counting directed acyclic graphs with the same partial ordering

Question

We are given a partially ordered set $P$. Let $L$ denote the set of all linear extensions of $P$ (or equivalently, the set of all topological sortings of the nodes).

We want to count the number of labeled DAGs which give rise to any of those linear extensions $L$.

For example, we are given a set of nodes $\{A,B,C\}$ and that $A < B$. The set of linear extensions $L$ is $\{ABC, ACB, CAB \}$. The number of DAGs with 3 nodes is 25, out of which 9 have a path from $A$ to $B$.

Has this problem been studied before? I was not able to find anything about it.

A related problem is that of counting the number of linear extensions of a given partially ordered set. This problem is #P-complete. Intuitively, my problem seems to be as hard as the one of counting linear extensions.

Edit: I probably gave a wrong formulation of my problem. I reformulated it to better match what I had in mind. I hope I got it right now.

Answer 1

Maybe I'm naive, but the minimal DAG (in the sense of contained in all other examples) for a given (finite) partial order must be its Hasse diagram: you cannot leave out any covering relations without changing the partial order. Also adding any subset of the missing directed edges to the Hasse diagram gives a DAG with the same partial order. So the answer would always be $2^k$ where $k$ is the number of relations that are in the partial order but are not cover relations. Then the problem is easy, since finding the Hasse diagram of a partial order is not hard.

Answer 2

I guess by your question about a DAG giving rise to a partial order, you're saying that given a DAG $G$, we create a partial order $\lhd$ such that $x \lhd y$ iff there is a path $x \rightarrow \ldots \rightarrow y$ in $G$.

Let's start by noting that any graph $G$ induces a relation $R$ -- the edge relation of $G$. If $G$ is a DAG, then $R$ is almost a partial order (it might not satisfy transitivity), but its transitive closure $R^*$ is certainly a partial order and in fact this is the partial order we generated above.

Since the vertices of all the graphs we might consider are identical, we only need to think about the edge relations. So our question reduces to "for a partial order $\lhd$, how many relations $R$ are there such that $R^* = \lhd$?".

To compute this number, let's introduce a new relation $\lhd_*$ which we'll define as the smallest relation such that $\lhd_*^* = \lhd$. Then it's pretty easy to see that the number of relations $R$ we can have is just $2^k$ where $k = \left| \lhd \setminus \lhd_* \right|$ is the number of edges that we can remove from $\lhd$ while still recovering $\lhd$ when taking the transitive closure.

Answer 3

Hm, here is a quick thought. It seems that all the DAGs that give rise to the same partial order contain the same "minimal" set of edges, and all the other edges are simply optional, giving you the total count as a power of 2.

As I understand, a directed acyclic graph $G=(V,E)$ gives rise to the partial order $\leqslant$ defined like this: $u \leqslant v$ iff there is a path (possibly empty) in $G$ leading from $u$ to $v$.

Definition. Suppose that $\leqslant$ is a partial order on a set $V$. Let's say that $u \in V$ immediately precedes $v \in V$ if $u < v$ and there is no $w \in V$ wuch that $u < w$ and $w < v$. (By $a < b$ we mean that $a \leqslant b$ and $a \neq b$).

Proposition. If DAG $G=(V,E)$ gives rise to a partial order $\leqslant$ on $V$ and vertex $u$ immediately precedes vertex $v$, then $(u,v)\in E$.

Proof. Suppose that $(u,v)\not\in E$. Since $u < v$, there is a path going from $u$ to $v$ that contains at least 2 edges. If $w$ is any intermediate vertex on this path, then $u<w$ and $w <v$, su $u$ does not immediately precede $v$, a contradiction.

So, we proved that if a DAG $(V, E)$ gives rise to the partial order $\leqslant$, then $E' \subset E \subset E''$, where $E'$ is the set of all $(u,v)$ such that $u$ immediately precedes $v$, and $E''$ is the set of all pairs $(u,v)$ such that $u < v$. And vice versa, any graph $(V, E)$ such that $E' \subset E \subset E''$ will give rise to $\leqslant$. So the total number of DAGs giving rise to $\leqslant$ is simply $2^{|E''|-|E'|}$.