5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

I was not able to turn up any better algorithm in my research.

In practice, you could improve the running time for many graphs by first decomposing the graph into strongly connected components, then running Floyd-Warshall on each strongly connected component. This does not improve the worst-case complexity (since in the worst case the entire graph could form one large strongly connected component), but it might help on many graphs you're likely to run into in practice.

$\endgroup$
  • $\begingroup$ I'm commenting on your answer since O.P is not active anymore. Just to make sure - OP asks about -simple- cycles? Since if we don't constrain the problem to simple cycles, we can find the relevant vertices by breaking the graph to strongly connected components, and then running BF on each component, returning the vertices that are part of a component that had a negative cycle. $\endgroup$ – Mickey Feb 17 '18 at 13:27
  • $\begingroup$ @Mickey, great point! I guess I implicitly assumed simple cycles without realizing it. Oops. Want to write an answer that covers the case of cycles that aren't required to be simple? Or I can edit my answer to incorporate your insight if you prefer -- I just want to give you first chance to write your own answer if you like. $\endgroup$ – D.W. Feb 17 '18 at 18:49
  • $\begingroup$ I have added my answer, feel free to correct/improve it if needed. $\endgroup$ – Mickey Feb 17 '18 at 21:26
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.