Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!magnus.ircc.ohio-state.edu!csn!ccncsu!animas!beaty
From: beaty@animas.lance.colostate.EDU (steve beaty)
Newsgroups: comp.theory
Subject: How many topological sorts are there in a given DAG?
Message-ID: <13066@ccncsu.ColoState.EDU>
Date: 21 Feb 91 00:12:00 GMT
Sender: news@ccncsu.ColoState.EDU
Reply-To: beaty@animas.lance.colostate.EDU (steve beaty)
Organization: Colorado State U. Center for Computer Assisted Engineering.
Lines: 23


	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.