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.