# Undirected Negative Cost Cycle Detection - Can Bellman-Ford Fail?

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?

• 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. Dec 16, 2016 at 3:01
• @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. Dec 16, 2016 at 7:35