We are assigning the colours white/black to the vertices of a DAG, under the condition that if $V$ is black and there is a path $V \to W$ for some vertex $W$, then $W$ is black.
- In the case of a linear chain of $N$ nodes, the answer is $N+1$ - either all the nodes are white, or one of the N nodes is black meaning all subsequent nodes in the chain are black.
- In the case of $N$ nodes and zero edges, the answer is $2^N$.
A trivial solution is to generate all valid of the graph colourings, and then count the number of them. This can be done recursively in exponential time.
I'm looking for an efficient solution to the above problem. There is a seemingly O(n) dynamic programming algorithm that solves this for trees; I wasn't able to generalise it for the arbitrary DAG case.