MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

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

share|cite|improve this answer
Couldn't have asked for a better answer. Thanks for the great reference. – haz Nov 15 '10 at 12:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.