Welcome to MathOverflow

Question

2

1

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?

edited Nov 12 2010 at 23:33

Ricky Demer
6,371●8●31

asked Nov 12 2010 at 23:16

haz
21●3

1

Oops. I should have paid attention to the tag. I clicked on this expecting DAG to mean Derived Algebraic Geometry. :( – Matt Nov 13 2010 at 1:52

Me too. Is DAG a standard acronym in graph theory? – Dr Shello Nov 13 2010 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 2010 at 6:00

Directed Acyclic Graph – Dan Ramras Nov 13 2010 at 17:54

Aye, Directed Acyclic Graph. Sorry for the confusion. – haz Nov 15 2010 at 12:47

mhum · Answer 1 · 2010-11-12 23:36:48Z UTC

3

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

answered Nov 12 2010 at 23:36

mhum
385●1●7

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

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.