How can you compute the number of topological sorts in a DAG?

If you have a DAG, G, a topological sort is just an ordering of the vertices such that if an edge x->y exists in G, then the index of x is less than the index of y.

It's not hard to figure out how a topological sort can be given, but how efficiently can one compute the total number of topological sorts that exist for a given acyclic graph?

-
Oops. I should have paid attention to the tag. I clicked on this expecting DAG to mean Derived Algebraic Geometry. :( – Matt Nov 13 '10 at 1:52
Me too. Is DAG a standard acronym in graph theory? – Dr Shello Nov 13 '10 at 4:09
Dr Shello: yes, DAG is a very standard abbreviation. It is often spoken as well and is pronounced to rhyme with "bag". – Warren Schudy Nov 13 '10 at 6:00
Directed Acyclic Graph – Dan Ramras Nov 13 '10 at 17:54
Aye, Directed Acyclic Graph. Sorry for the confusion. – haz Nov 15 '10 at 12:47

1 Answer

This problem is #P-complete. See "Counting linear extensions is #P-complete", G. Brightwell and P. Winkler, Proc. 23rd ACM Symposium on the Theory of Computing, 1991

-
Couldn't have asked for a better answer. Thanks for the great reference. – haz Nov 15 '10 at 12:49