25-2 Shortest paths in epsilon-dense graphs

A graph $G = (V, E)$ is $\epsilon$-dense if $|E| = \Theta(V^{1 + \epsilon})$ for some constant $\epsilon$ in the range $0 < \epsilon \le 1$. By using $d$-ary min-heaps (see Problem 6-2) in shortest-paths algorithms on $\epsilon$-dense graphs, we can match the running times of Fibonacci-heap-based algorithms without using as complicated a data structure.

a. What are the asymptotic running times for $\text{INSERT}$, $\text{EXTRACT-MIN}$, and $\text{DECREASE-KEY}$, as a function of $d$ and the number $n$ of elements in a $d$-ary min-heap? What are these running times if we choose $d = \Theta(n^\alpha)$ for some constant $0 < \alpha \le 1$? Compare these running times to the amortized costs of these operations for a Fibonacci heap.

b. Show how to compute shortest paths from a single source on an $\epsilon$-dense directed graph $G = (V, E)$ with no negative-weight edges in $O(E)$ time. ($\textit{Hint:}$ Pick $d$ as a function of $\epsilon$.)

c. Show how to solve the all-pairs shortest-paths problem on an $\epsilon$-dense directed graph $G = (V, E)$ with no negative-weight edges in $O(VE)$ time.

d. Show how to solve the all-pairs shortest-paths problem in $O(VE)$ time on an $\epsilon$-dense directed graph $G = (V, E)$ that may have negative-weight edges but has no negative-weight cycles.

a.

• $\text{INSERT}$: $\Theta(\log_d n) = \Theta(1 / \alpha)$.
• $\text{EXTRACT-MIN}$: $\Theta(d\log_d n) = \Theta(n^\alpha / \alpha)$.
• $\text{DECREASE-KEY}$: $\Theta(\log_d n) = \Theta(1 / \alpha)$.

b. Dijkstra, $O(d\log_d V \cdot V + \log_d V \cdot E)$, if $d = V^\epsilon$, then

$$ \begin{aligned} O(d \log_d V \cdot V + \log_d V \cdot E) & = O(V^\epsilon \cdot V / \epsilon + E / \epsilon) \\ & = O((V^{1+\epsilon} + E) / \epsilon) \\ & = O((E + E) / \epsilon) \\ & = O(E). \end{aligned} $$

c. Run $|V|$ times Dijkstra, since the algorithm is $O(E)$ based on (b), the total time is $O(VE)$.

d. Johnson's reweight is $O(VE)$.