Return to 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)$

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)$

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)$

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)$

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?

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)$