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?

Improve this question
$\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
    Commented Nov 13, 2010 at 1:52
  • $\begingroup$ Me too. Is DAG a standard acronym in graph theory? $\endgroup$
    – Dr Shello
    Commented 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$
    – Warren Schudy
    Commented Nov 13, 2010 at 6:00
  • $\begingroup$ Directed Acyclic Graph $\endgroup$
    – Dan Ramras
    Commented Nov 13, 2010 at 17:54
  • $\begingroup$ Aye, Directed Acyclic Graph. Sorry for the confusion. $\endgroup$
    – haz
    Commented Nov 15, 2010 at 12:47

1 Answer 1

Reset to default
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

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

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