Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

1 Answer 1

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|improve this answer
    
Couldn't have asked for a better answer. Thanks for the great reference. –  haz Nov 15 '10 at 12:49
add comment

Your Answer

 
discard

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.