*Bounty: 50*

*Bounty: 50*

I am given a directed acyclic graph $G = (V,E)$, which can be assumed to be topologically ordered (if needed). The edges in G have two types of costs – a nominal cost $w(e)$ and a spiked cost $p(e)$.

The goal is to find a path from a node $s$ to a node $t$ that minimizes the following cost: $$sum_e w(e) + max_e {p(e)},$$ where the sum and maximum are taken over all edges of the path.

Standard dynamic programming methods show that this problem is solvable in $O(E^2)$ time. Is there a more efficient way to solve it? Ideally, an $O(Ecdot operatorname{polylog}(E,V))$ algorithm would be nice.

—- EDIT —–

This is the $O(E^2)$ solution I found using dynamic programming, if it’ll help.

First, order all costs $p(e)$ in an ascending order. This takes $O(Elog(E))$ time.

Second, define the state space consisting of states $(x,i)$ where $x$ is a node in the graph and $iin {1,2,…,|E|}$. It represents "We are in node $x$, and the highest edge weight $p(e)$ we have seen so far is the $i$-th largest".

Let $V(x,i)$ be the length of the shortest path (in the classical sense) from $s$ to $x$, where the highest $p(e)$ encountered was the $i$-th largest. It’s easy to compute $V(x,i)$ given $V(y,j)$ for any predecessor $y$ of $x$ and any $j in {1,…,|E|}$ (there are two cases to consider – the edge $yto x$ is has the $j$-th largest weight, or it does not).

At every state $(x,i)$, this computation finds the minimum of about $deg(x)$ values. Thus the complexity is $$O(E) cdot sum_{xin V} deg(x) = O(E^2)$$, as each node is associated to $|E|$ different states.