Combinatorics: how many ways can we mark nodes in a DAG as black or white, if every node downstream of a black node is also black?

Question

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.

Examples:

• 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.

Answer 1

Your problem is #P-complete. The set of solutions can be identified with the set of antichains with the poset corresponding to the DAG (the correspondence identifies a coloring with the black vertices that have no black parents), counting the number of which has been shown to be #P-complete by Provan and Ball in The complexity of counting cuts and of computing the probability that a graph is connected.