A Bottom-Up Algorithm for Negative-Weight
SSSP with Integrated Negative Cycle Finding

Consider a SCC $C$ of $H\setminus S_{(H,d)}$ with $|C|>\frac{3}{4}|V(H)|$. Lemma 2 guarantees that, for every vertex $v\in C$, both the in-ball and out-ball of radius $\frac{d}{4}$ centered at $v$ in $H_{\geq 0}$ contain more than $\frac{|V(H)|}{2}$ vertices. Let $u,v\in C$. Since both the out-ball of radius $\frac{d}{4}$ centered at $u$ and the in-ball of radius $\frac{d}{4}$ centered at $v$ each contain more than $\frac{|V(H)|}{2}$ vertices, their intersection must be non-empty. Therefore, there exists $w\in V(H)$ such that there exists a path from $u$ to $w$ of length at most $\frac{d}{4}$ in $H_{\geq 0}$, and a path from $w$ to $v$ of length at most $\frac{d}{4}$ in $H_{\geq 0}$. By concatenating these two paths, we obtain a path from $u$ to $v$ of length at most $\frac{d}{2}$ in $H_{\geq 0}$. Since $H_{\geq 0}\subseteq G^{\prime}_{\geq 0}$, this result extends to $G^{\prime}_{\geq 0}$. Therefore, the diameter of $C$ is at most $\frac{d}{2}$ in $H_{\geq 0}$ (and in $G^{\prime}_{\geq 0}$), as desired. ∎

Since $(H,d)$ is not the root, $H$ is a strongly connected component (SCC) of its parent $H^{\prime}$. If $V(H)>\frac{3}{4}|V(H^{\prime})|$, then by Claim 6, $V(H)$ has diameter at most $d$ in $H_{\geq 0}$, and hence in $G^{\prime}_{\geq 0}$. Otherwise, its parent node $(H^{\prime},d)$ has the same diameter parameter $d<d_{0}$. By induction, $V(H^{\prime})$ has diameter at most $d$ in $G^{\prime}_{\geq 0}$. Since $V(H)$ is a subset of $V(H^{\prime})$, it also has diameter at most $d$ in $G^{\prime}_{\geq 0}$. Therefore, in both cases, $V(H)$ has diameter at most $d$ in $G^{\prime}_{\geq 0}$, as desired. ∎

Let $\text{neg}_{H}(P)\leq 0$ denote the total negative weight (i.e., sum of negative-weight edges) of $P$ in $H$. For a simple path $P$ in $H$ with $w_{H}(P)\leq 0$, each negative-weight edge in $H$ has weight at least $-W/2$, and $P$ contains at most $\lvert V(H)\rvert\leq n$ edges. Therefore, $\text{neg}_{H}(P)\geq-W/2\cdot n=-d_{0}$. In $H_{\geq 0}$, all negative-weight edges are replaced with edges of weight 0. Hence, the weight of $P$ in $H_{\geq 0}$ is given by $w_{H_{\geq 0}}(P)=w_{H}(P)+\lvert\text{neg}_{H}(P)\rvert$. Substituting $w_{H}(P)\leq 0$ and $\lvert\text{neg}_{H}(P)\rvert\leq W/2\cdot n=d$, we find $w_{H_{\geq 0}}(P)\leq d$, as desired. ∎

Suppose there exists a path $P$ in $H$ such that $w_{H}(P)\leq 0$ but $w_{H_{\geq 0}}(P)>d$. Let $\text{neg}_{H}(P)$ denote the total negative weight of $P$ in $H$. The weight of $P$ in $H_{\geq 0}$ is given by $w_{H_{\geq 0}}(P)=w_{H}(P)+\lvert\text{neg}_{H}(P)\rvert$. Since $w_{H}(P)\leq 0$ and $w_{H_{\geq 0}}(P)>d$, it follows that $\lvert\text{neg}_{H}(P)\rvert>d$. For each negative-weight edge $e$ in $H$, its weight in $G$ is $w_{G}(e)=w_{H}(e)-W/2\leq w_{H}(e)-|w_{H}(e)|$, so the weight of $P$ in $G$ is $w_{G}(P)\leq w_{H}(P)-\lvert\text{neg}_{H}(P)\rvert$. Substituting $w_{H}(P)\leq 0$ and $\lvert\text{neg}_{H}(P)\rvert>d$, we find $w_{G}(P)<-d$. By Claim 7, $V(H)$ has diameter at most $d$ in $G^{\prime}_{\geq 0}$, so the shortest path $P^{\prime}$ in $G^{\prime}_{\geq 0}$ from the end of $P$ back to its start satisfies $w_{G^{\prime}_{\geq 0}}(P^{\prime})\leq d$. Since edge weights can only be smaller in $G$, we also have $w_{G}(P^{\prime})\leq d$. Combining $P$ and $P^{\prime}$ forms a cycle $C=P+P^{\prime}$ in $G$ with $w_{G}(C)=w_{G}(P)+w_{G}(P^{\prime})<-d+d=0$, so $C$ is a negative-weight cycle. ∎

Follows directly from Lemma 2. ∎

There are two cases to consider:

Case 1: For each vertex $v\in V(H)$, there exists a shortest path to $v$ of weight at most $d$ in $H_{\geq 0}$. In this case, the shortest path $P$ to $v$ with $w_{H_{\geq 0}}(P)\leq d$ has an expected $O(\log n)$ edges inside $S_{(H,d)}$ by Claim 10. Since $H_{\phi}$ has non-negative weight edges outside of $S_{(H,d)}$, we have $\mathbb{E}[\eta_{H,\phi}(v)]\leq O(\log n)$ for the parameter $\eta_{H,\phi}$ defined in Lemma 3. By Lemma 3, BellmanFordDijkstra runs in expected time $O(\sum_{v}(\deg_{H}(v)+\log\log n)\cdot\eta_{H,\phi}(v)),$ which has expectation $O((m_{H}+n_{H}\log\log n_{H})\log n)$ since $\mathbb{E}[\eta_{H,\phi}(v)]\leq O(\log n)$ for all $v\in V(H)$. Note that BellmanFordDijkstra can still terminate early and output a negative-weight cycle in $G$, but that only speeds up the running time.

Case 2: For some vertex $v\in V(H)$, every shortest path to $v$ has weight more than $d$ in $H_{\geq 0}$. By Claim 9, this implies the existence of a negative-weight cycle in $G$. Among all shortest paths to $v$, let $Q$ be one minimizing $w_{H_{\geq 0}}(Q)$, which is still greater than $d$. Take the longest prefix $Q^{\prime}$ of $Q$ with weight at most $d$ in $H_{\geq 0}$. Since $w_{H_{\geq 0}}(Q^{\prime})\leq d$, the number of edges of $Q^{\prime}$ inside $S_{(H,d)}$ has expectation $O(\log n)$ by Claim 10. Let $Q^{\prime\prime}$ be the path $Q^{\prime}$ concatenated with the next edge in $Q$, so that $w_{H_{\geq 0}}(Q^{\prime\prime})>d$ and the number of edges of $Q^{\prime\prime}$ inside $S_{(H,d)}$ still has expectation $O(\log n)$. Since $Q^{\prime\prime}$ is a prefix of shortest path $Q$, it is also a shortest path. Let $u\in V(H)$ be the endpoint of $Q^{\prime\prime}$, and let $i$ be the number of iterations of BellmanFordDijkstra before $d_{i}(u)=w_{H}(Q^{\prime\prime})$, so that $i$ has expected value $O(\log n)$. After $i$ iterations, BellmanFordDijkstra finds a shortest path $P$ ending at $u$ with $w_{H}(P)=d_{i}(u)=w_{H}(Q^{\prime\prime})$. Moreover, $w_{H_{\geq 0}}(P)\geq w_{H_{\geq 0}}(Q^{\prime\prime})$ since otherwise, replacing the prefix $Q^{\prime\prime}$ of $Q$ by $P$ results in a shortest path to $v$ of lower weight in $H_{\geq 0}$, contradicting the assumption on $Q$. It follows that after an expected $O(\log n)$ iterations of BellmanFordDijkstra, a path $P$ is found with $w_{H}(P)\leq 0$ and $w_{H_{\geq 0}}(P)>d$, and the algorithm terminates with a negative-weight cycle. The runtime is $O((m_{H}+n_{H}\log\log n_{H})\cdot i)$, which has expectation $O((m_{H}+n_{H}\log\log n_{H})\log n)$. ∎

There are two cases to consider:

Case 1: $H$ contains a negative-weight cycle consisting entirely of non-positive-weight edges. Since Decompose only removes positive-weight edges, such a cycle remains intact throughout the decomposition and persists in one of the leaf nodes. A negative-weight edge from this cycle is found in this leaf node, and the algorithm computes a negative-weight cycle and terminates early. In particular, the node $(H,d)$ is never processed.

Case 2: All negative-weight cycles in $H$ include at least one positive-weight edge. This case is the most subtle and requires carefully defining a reference path $Q$.

Define $M=-(d+1)\cdot|V(H)|\cdot W$. We first claim that any (potentially non-simple) path in $H$ of weight at most $M$ in $H$ must have weight exceeding $d$ in $H_{\geq 0}$. Given such a path, we first remove any cycles on the path of non-negative weight in $H$. The remaining path still has weight at most $M=-(d+1)\cdot|V(H)|\cdot W$, so it must have at least $(d+1)\cdot|V(H)|$ edges, which means it can be decomposed into at least $d+1$ negative-weight cycles, each with at least one positive-weight edge in $H_{\geq 0}$. It follows that the path has weight at least $d+1$ in $H_{\geq 0}$, concluding the claim.

Among all paths of weight at most $M$ in $H$, let $Q$ be one with minimum possible weight in $H_{\geq 0}$, which must be greater than $d$. Take the longest prefix $Q^{\prime}$ of $Q$ with weight at most $d$ in $H_{\geq 0}$. Since $w_{H_{\geq 0}}(Q^{\prime})\leq d$, the number of edges of $Q^{\prime}$ inside $S_{(H,d)}$ has expectation $O(\log n)$ by Claim 10. Let $Q^{\prime\prime}$ be the path $Q^{\prime}$ concatenated with the next edge in $Q$, so that $w_{H_{\geq 0}}(Q^{\prime\prime})>d$ and the number of edges of $Q^{\prime\prime}$ inside $S_{(H,d)}$ still has expectation $O(\log n)$. Let $u\in V(H)$ be the endpoint of $Q^{\prime\prime}$, and let $i$ be the number of iterations of BellmanFordDijkstra before $d_{i}(u)\leq w_{H}(Q^{\prime\prime})$, so that $i$ has expected value $O(\log n)$. After $i$ iterations, BellmanFordDijkstra finds a path $P$ ending at $u$ with $w_{H}(P)=d_{i}(u)\leq w_{H}(Q^{\prime\prime})$. Moreover, $w_{H_{\geq 0}}(P)\geq w_{H_{\geq 0}}(Q^{\prime\prime})$ since otherwise, replacing the prefix $Q^{\prime\prime}$ of $Q$ by $P$ results in a path of lower weight in $H_{\geq 0}$ and of weight at most $M$ in $H$, contradicting the assumption on $Q$. It follows that after an expected $O(\log n)$ iterations of BellmanFordDijkstra, a path $P$ is found with $w_{H}(P)\leq 0$ and $w_{H_{\geq 0}}(P)>d$, and the algorithm terminates with a negative-weight cycle. The runtime is $O((m_{H}+n_{H}\log\log n_{H})\cdot i)$, which has expectation $O((m_{H}+n_{H}\log\log n_{H})\log n)$. ∎

We first consider the decomposition phase. For each node $(H,d)$, the decomposition takes expected time $O((m_{H}+n_{H}\log\log n_{H})\log n)$ by Lemma 2. At each level of the decomposition tree, the total number of edges and vertices across all nodes is bounded by $m$ and $n$, respectively, so the expected runtime per level is $O((m+n\log\log n)\log n)$. With $O(\log n)$ levels in the decomposition tree, the total expected runtime is $O((m+n\log\log n)\log^{2}n)$.

For processing each node $(H,d)$, Lemma 4 adjusts $\phi$ in $O(n_{H}+m_{H})$ time, and Lemmas 11 and 12 establish an expected runtime of $O((m_{H}+n_{H}\log\log n_{H})\log n)$ for BellmanFordDijkstra. There may be an additional $O(m+n\log\log n)$ time to output a negative-weight cycle, but this only happens once. Again, summing over all nodes $(H,d)$, the total expected runtime is $O((m+n\log\log n)\log^{2}n)$.

To convert distances in $G^{\prime}$ into a reweighted graph $G_{\phi}$ with edge weights at least $-W/2$, we note that setting $\phi$ as the distances in $G^{\prime}$ makes $G^{\prime}_{\phi}$ non-negative. Since $w_{G^{\prime}}(e)=w_{G}(e)+W/2$ for all $e\in E$, it follows that $w_{G_{\phi}}(e)=w_{G^{\prime}_{\phi}}(e)-w_{G^{\prime}}(e)+w_{G}(e)\geq-W/2$, as desired. ∎