6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A.k.a. "counting downsets in a partial order". $\endgroup$ – David Richerby Nov 15 '17 at 13:28

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.