Negative Weight Cycle Algorithm

Question

I was thinking about the algorithm of finding a negative weight cycle in a directed graph. The Problem is: we have a graph G(V,E), we need to find an efficient algorithm to find a cycle with negative weight. I understand the algorithm in this PDF document

Briefly, the algorithm is applying Bellman Ford algorithm by iterating |V|-1 times doing relaxations. Afterwards it checks if there is an edge that can be even relaxed more, then a negative weight cycle exists and we can trace it back by parent pointers and everything goes well, we find a negative weight cycle.

However, I was thinking of another algorithm of just using depth-first search (DFS) on the graph by keeping track of the sum so far of the distances you traversed, I mark all nodes white at the beginning and make them grey when I am searching a path, and mark them black when they are finished, that way I know that I find a cycle if and only if I find a visited node and it is grey (in my path) , not black which was already finished by the Depth-First search, and so for my algorithm, if I reach a grey node that has already been visited, I check what would it's update be (the new distance) and if it is lower than before, I know that I have a negative weight cycle and can trace it back.

Is my algorithm wrong? If so, can you find a counterexample ? If not can you help me prove it?

Thank You

Exerciser

In order to find a -ve cycle, algorithms like this must traverse it. I suspect that in a large graph, there are an very large number of possible cycles. In a fully connected graph with N nodes there will N!/N cycles that start from the first node and visit each of the other nodes in turn. So I think your algorithm must either take a much longer time than Bellman-Ford or miss some cycles in some graphs. – Equitable

do you do dfs from every node? if not, what nodes do you begin the search from? – Mycenae

my dfs traversed all the nodes, when it is stuck, it finds another node with 0 in-degree and does dfs again. Overall my DFS should run in O(V+ E) time (linear) – Exerciser

Answer 1

One clear problem, you're marking the nodes.

 A <--->   B
 |         ^ 
   \--\    |  
           v    
       ->  D  (crap ascii art, A  connects to D unidirectionally)

Suppose you take path A->B->D, A B D are grey when you hit D. No cycle is found. You pop out to A; B and D are black. You take the edge, no cycle is found because D is black.

In general, the number of paths is exponential to the size of the graph. You'd have to try every path, there's no way to mark nodes here. If you treated each edge direction in directed graph separately, I believe you'd be able to do this marking the edges, however, this is equivalent to enumerating all paths.

Distich

Answer 2

Bellman Ford doesn't always work, the problem is its a single source shortest path algorithm, if the negative loop is not reachable from the source you pick, it fails. However a little change to Bellman Ford could help, instead of selecting a source vertex and initialise its distance to 0, we can initialise all the distance to 0 and then run Bellman Ford. This is equivalent to add a extra vertex s' which points to all the vertexes in the original graph with 0 weight edge. Once Bellman Ford is run on the graph and we found any vertex u and edge (u,v) that make d[u] + w[u][v] < d[v], we know there must be a negative cycle leading to u, tracking back from u in the predecessor graph and we'll find the cycle.

DFS is not gonna work in any way, it's obviously not able to exhaust all possible cycles. DFS can be used to find the presence of cycle in graph, but no more.

Lialiabilities

Could you tell more about the tracking back? The cycle found via tracking back must be the negative cycle? Dose it mean, if there d[u] + w[u][v] < d[v] is not satisfied, then there is no cycle in the predecessor graph? – Taiga

@Taiga The predecessor graph has one edge for each vertex. Any graph with n vertices will have a cycle, so the predecessor graph has a cycle. And BF never produces nonnegative cycles, so we're guaranteed to find a negative cycle. – Curcio

Answer 3

Yamada/Kinoshitas Algorithm from 2003 solves the problem of finding all negative weighted cycles in a directed weighted graph using upper limits on the max-vertices count of a detected cycle.

It is quite challenging to implement, though.

Abstract

Given a directed graph where edges are associated with weights which are not necessarily positive, we are concerned with the problem of finding all the elementary cycles with negative total weights. Algorithms to find all the elementary cycles, or to detect, if one exists, a negative cycle in such a graph are well explored. However, finding all the elementary cycles with negative cost appears to be unexplored. We develop an algorithm to do this based on the “divide-and-conquer” paradigm, and evaluate its performance on some numerical experiments.

From May 2002 Discrete Applied Mathematics 118(3):279-291 https://www.researchgate.net/publication/220570430_Finding_all_the_negative_cycles_in_a_directed_graph

Boldt

Answer 4

I believe there is a way to solve this in linear time. While searching the graph with depth-first-search (DFS has a runtime of O(V+E)), you can keep track of the distance from the source to the current node (by simply incrementing the parent's distance with the weight of the edge connecting the child node to the parent). Then, whenever you encounter a cycle (cycles are discovered through finding a back edge in an undirected graph or either a back edge or a forward edge in a directed graph), you can subtract the distance between the source node and the root node of the cycle from the distance between the source node and the final node in the cycle (the root node being the node where the cycle began). If the result is negative, the cycle must be negative!

Achaean