[comp.theory] How many topological sorts are there in a given DAG?

beaty@animas.lance.colostate.EDU (steve beaty) (02/21/91)

	be forewarned, i'm out of my depth here :-)

	i would like to know whether it's been shown that any method 
that finds the number of topological sorts of a directed acyclic graph is
NP-complete.  i have a method that produces the result but i'd like to
know how hard the problem really is.  my intuition says it's
NP-complete, but my intuition proves nothing (un)fortunately ;-)

	i think the problem statement would go something like:

	given a DAG D = (V,E) and a number K <= |V!|, is there less
	than K topological sorts of D?

	basically, can i find out how many different topological
sorts are possible in a DAG in polynomial time?  thanks much for any
insight.


		steve beaty@longs.lance.colostate.edu

disk-claimer: n. a small computer program that removes all traces of my
employer's responsibility from all media containing these lines.