0
$\begingroup$

this question is a follow-up to Detecting Negative Cycles in Undirected Graphs.

When checking publications related to the problem of detecting negative cycles in weighted, undirected graphs (the apparently newest one being this one ), I saw only $b$-matching and $T$-joins being mentioned and investigated as methods for that problem.

Question:
Are there concrete examples of undirected, weighted graphs, that contain negative-cost cycles, wich the Bellman-Ford algorithm fails to detect, resp. can the existence of such graphs be proven?

Improve this question
$\endgroup$
2
  • $\begingroup$ Now reading your linked post closer it seems you are not using standard Bellman-Ford because you are modifying it to get around the problem I mention in my answer. So, my answer below applies to usual Bellman-Ford, but maybe not what you have in mind. $\endgroup$
    – John Machacek
    Dec 16, 2016 at 3:01
  • $\begingroup$ @JohnMachacek what I am actually trying find out, whether $b$-matching or $T$-joins are inevitable or, whether "minor" modifications, that safe-guard against using an edge in both directions in the shortest paths tree, can make the Bellman-Ford algorithm usable for detecting "true" negative cycles in undirected graphs. $\endgroup$
    – Manfred Weis
    Dec 16, 2016 at 7:35

1 Answer 1

Reset to default
2
$\begingroup$

If an undirected graph has a negative weight cycle, then the Bellman-Ford algorithm will detect it. However, if an undirected graph does not have a negative weight cycle the Bellman-Ford algorithm may still detect one. So, the answer to your specific question in the body is no (there are no false negatives) while the answer to the general question is yes (there may be false positives). In fact Bellman-Ford can only really be used with nonnegative weights for undirected graphs.

The Bellman-Ford algorithm works on directed graphs. To make it work with undirected graphs we must make each undirected edge into two directed edges (one in each direction) with the same weights as the original undirected edge. Now any negative weight undirected cycle is transformed into a negative weight directed cycle, and hence would be detected. In any negative weight edge is transformed in a negative weight cycle of length two! Thus Bellman-Ford will always detect a negative cycle if there is any negative weight edge.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.