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$ 11 Answer
$\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.
$\endgroup$ 2
