> 
> chase@pine.ece.utexas.edu (Craig M. Chase) writes:
> > I've not looked at this algorithm to figure out exactly what's going
> > on.   Perhaps the explanation is that finding the largest cycle on a
> > *weighted* graph is NP-hard, but that finding the largest cycle on a
> > graph with unit edge weights is polynomial?  The dependence graph for
> > tsort is unweighted, yes?
> 
> Finding a cycle in a graph has nothing to do with whether or not the
> edges are weighted.  A cycle is a cycle, pure and simple.  Think about
> it.
> Email: Mark_Weaver@brown.edu           | Brown University

OK, I have.

Subtle changes in a problem can often make the difference between it
being tractable or intractable.  The existence of edge weights can
certainly make a significant difference.  

However, Mark is (mostly) correct in this instance.

From Garey and Johnson, "Computers and Intractability: A Guide to the
Theory of NP-Completeness", page 213, in the list of known NP-complete
problems.

Longest Circuit:
  Instance: Graph G = (V,E), length l(e) for each edge e in E and
    a positive integer K.
  Question: Is there a simple circuit in G of length K or more, i.e.
  whose edge lengths sum to at least K

  in the comments: remains NP-complete if l(e) = 1 for all edges as
  does the corresponding problem for directed circuits in directed
  graphs.  The directed problem with all l(e) = 1 can be solved in
  polynomial time if G is a "tournament".

Perhaps dependence graphs are "tournaments", I'll see if I can't find
the reference and find out.  If anyone actually cares, they can email
me for the answer.  I've already wasted more than my share of
bandwidth on this subject.

Oh, one more thing, In case anybody cares, the shortest circuit is
polynomial when all edge weights l(e) are positive, but NP-complete
when negative weights are allowed.  

Also in case anybody cares, it is incorrect to describe an
optimization problem as NP-complete.  Only decision problems with
"Yes/No" (e.g. "does a solution exist of size K") answers can properly
be termed NP-complete.  Optimization problems (e.g. "find the best
solution") are usually "NP-Hard".  In polite company (and most
journals) incorrect but well intentioned uses of "NP-complete" are
accepted.


Craig



------------------------------------------------------------------------------