patternMinor
Finding all vertices on negative cycles
Viewed 0 times
allnegativefindingverticescycles
Problem
Given a weighted digraph, I can check whether a given vertex belongs to a negative cycle in $O(|V|\cdot|E|)$ using Bellman-Ford. But what if I need to find all vertices on negative cycles? Is there a way to do it faster than Floyd-Warshall's $O(|V|^3)$?
Solution
If you don't constrain yourself to simple cycles, you can actually use the Bellman-Ford algorithm to find all the relevant vertices.
Start by running a DFS on the graph to find its strongly connected components. Let them be $G_1,G_2,...G_k$. For each $G_i$, run BF on the subgraph. If the BF algorithms detects a negative cycle (which it can after $|V_i|+1$ iterations where $V_i$ is the vertices in $G_i$), add $V_i$ to your list of vertices that belong to a negative (not necessarily simple) cycle.
If one of the strongly connected components contain a negative cycle, then because $G_i$ is finite and so are the weights, you can loop through the negative cycle as much as you need, and then add go in a cycle through all the vertices in $G_i$. You only need to loop an amount that will guarantee a total negative cycle.
It is easy to show that there are no cycles between any $G_i,G_j$ and therefore there are no negative cycles other than inside the strongly connected components.
Since you run BF on each subgraph seperately, you keep the time complexity of BF which is $O(|V|\cdot|E|)$.
Start by running a DFS on the graph to find its strongly connected components. Let them be $G_1,G_2,...G_k$. For each $G_i$, run BF on the subgraph. If the BF algorithms detects a negative cycle (which it can after $|V_i|+1$ iterations where $V_i$ is the vertices in $G_i$), add $V_i$ to your list of vertices that belong to a negative (not necessarily simple) cycle.
If one of the strongly connected components contain a negative cycle, then because $G_i$ is finite and so are the weights, you can loop through the negative cycle as much as you need, and then add go in a cycle through all the vertices in $G_i$. You only need to loop an amount that will guarantee a total negative cycle.
It is easy to show that there are no cycles between any $G_i,G_j$ and therefore there are no negative cycles other than inside the strongly connected components.
Since you run BF on each subgraph seperately, you keep the time complexity of BF which is $O(|V|\cdot|E|)$.
Context
StackExchange Computer Science Q#12243, answer score: 6
Revisions (0)
No revisions yet.