13
$\begingroup$

If you have a directed acyclic graph (DAG) $G$, a topological sort is just an ordering of the vertices such that if an edge $x \to 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?

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

1 Answer 1

13
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Couldn't have asked for a better answer. Thanks for the great reference. $\endgroup$
    – haz
    Nov 15, 2010 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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