7
$\begingroup$

Given a directed and acyclic graph G(V,E) is there any way to determine the exact number of topological orderings it can have? I know the minimum is 1 if it contains a Hamiltonian path, but can the maximum number be determined ?

$\endgroup$
  • 1
    $\begingroup$ Assuming that the graph is directed and acyclic (which is has to be for a topological ordering to make sense), if the graph has a Hamiltonian path then there is a $\mathit{unique}$ topological sort ordering, not just a minimum of $1$. $\endgroup$ – Peter Woolfitt May 29 '14 at 20:33
8
$\begingroup$

Of course there is a way -- just enumerate all of the topological orderings and count them as you go!

On the other hand, this is very slow. The general problem of determining the exact count in reasonable time is usually phrased as counting the linear extensions of a partial order, and is known to be hard. More precisely, it is #P-complete, so it cannot be done in polynomial time unless P=NP.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Let me rephrase it a little then, are there any types of directed and acyclic graphs for which the number topological orderings can be easily determined ? $\endgroup$ – Alex May 29 '14 at 20:50
  • 2
    $\begingroup$ @Alex Yes, for example if the graph looks like Young tableau, then you can use the hook length formula. Of course, there are also other special cases, but that one is perhaps the most interesting. $\endgroup$ – dtldarek May 29 '14 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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