Detecting Negative Cycles in Undirected Graphs

Question

I recently faced the problem of quickly detecting negative cycles in undirected, weighted graphs. Resorting to the Bellman-Ford Algorithm, as commonly suggested, turned out to be very inefficient and also needed some care to prevent the algorithm from ping ponging between a pair of vertices adjacent to a negative edge.
Another thing about using the Bellman-Ford algorithm for detecting negative cycles is that it requires $O(n^3)$ preprocessing before it allows the detection of negative cycles, not to mention that experiments suggest, that it gets "stuck" in a single such cycle.

Now my idea would be to

• calculate the graph's MST

• calculate the all pairs shortest path distances of the MST

• report the existence of a negative cycle, if an edge can be found, for which $(u,v)\in E\setminus\{ E\cap MST\}$ and $dist_{MST}(u,v)+w(v,u) \lt 0$ holds.

the complexity would be $O(n^2)$ instead of $O(n^3)$, but:

Questions

• would the algorithm sketched above correctly report the existence of negative cycles, resp. in which cases will it fail?

• is the set of edges that are not in the MST, but whose union with the edges on the shortest MST-path between their adjacent vertices is a negative cycle, represent a negative-cycle transversal of the graph?

Addendum
In the abstract of this article it is stated, that the problem of detecting negative cost cycles in undirected graphs (UNCCD problem) is "significantly harder than the corresponding problem in directed graphs" and the complexities of different algorithms are given, ranging from $O(n^{2.75}\log n)$ to $O(n^6)$

Answer 1

Unfortunately, the answer is negative in the general case!

Counterexamples can be easily constructed in the following way:

• take a graph, that resembles a tree with at least one sufficiently long shortest path.

• assign to each tree-edge weight $1$, and $-k\ < -2$ to two edges $e$ and $f$, which are at least $2k-2$ edges of weight $1$ apart.

• insert two edges, that are not tree edges and resemble a perfect matching on the vertices adjacent to the two negative edges and assign weight $2$ to both edges.

With the above construction, we have created a negative cycle of length $-2k-2+4\ < -2$ that contains two non-tree edges.
The shortest cycle containing only a single non-tree edge and both negative edges is however $\ > (-2k)\ +\ (2k-2)\ +\ (2) \ge\ 0$.

This demonstrates that negative cycles may go undetected with the $MST$-heuristic; it may however still be useful as a fast sufficient check for negative cycles.