Lesson plan

Zero-weight cycle problem

In computer science and graph theory, the zero-weight cycle problem is the problem of deciding whether a directed graph with weights on the edges (which may be positive or negative or zero) has a cycle in which the sum of weights is 0. A related problem is to decide whether the graph has a negative cycle, a cycle in which the sum of weights is less than 0. This related problem can be solved in polynomial time using the Bellman–Ford algorithm. If there is no negative cycle, then the distances found by the Bellman–Ford algorithm can be used, as in Johnson's algorithm, to reweight the edges of the graph in such a way that all edge weights become non-negative and all cycle lengths remain unchanged. With this reweighting, a zero-weight cycle becomes trivial to detect: it exists if and only if the zero-weight edges do not form a directed acyclic graph. Therefore, the special case of the zero-weight cycle problem, on graphs with no negative cycle, has a polynomial-time algorithm. In contrast, for graphs that contain negative cycles, detecting a simple cycle of weight exactly 0 is an NP-complete problem. This is true even when the weights are integers of polynomial magnitude.…

Back to article

Article summary

In computer science and graph theory, the zero-weight cycle problem is the problem of deciding whether a directed graph with weights on the edges (which may be positive or negative or zero) has a cycle in which the sum of weights is 0. A related problem is to decide whether the graph has a negative cycle, a cycle in which the sum of weights is less than 0. This related problem can be solved in polynomial time using the Bellman–Ford algorithm. If there is no negative cycle, then the distances found by the Bellman–Ford algorithm can be used, as in Johnson's algorithm, to reweight the edges of the graph in such a way that all edge weights become non-negative and all cycle lengths remain unchanged. With this reweighting, a zero-weight cycle becomes trivial to detect: it exists if and only if the zero-weight edges do not form a directed acyclic graph. Therefore, the special case of the zero-weight cycle problem, on graphs with no negative cycle, has a polynomial-time algorithm. In contrast, for graphs that contain negative cycles, detecting a simple cycle of weight exactly 0 is an NP-complete problem. This is true even when the weights are integers of polynomial magnitude.…

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.