# Shortest Path in a Directed Acyclic Graph with two types of costs

I am given a directed acyclic graph $$G = (V,E)$$, which can be assumed to be topologically ordered (if needed). Each edge $$e$$ in G has two types of costs - a nominal cost $$w(e)$$ and a spiked cost $$p(e)$$. I am also given two nodes in $$G$$, node $$s$$ and node $$t$$.

The goal is to find a path from $$s$$ to $$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(E\cdot \operatorname{polylog}(E,V))$$ algorithm would be nice.

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(E\log(E))$$ time.

Second, define the state space consisting of states $$(x,i)$$ where $$x$$ is a node in the graph and $$i\in \{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 $$y\to 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_{x\in V} \deg(x) = O(E^2),$$ as each node is associated to $$|E|$$ different states.

New contributor
Miel Sharf is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• @BernardoSubercaseaux, you can add a constant to all $p(e)$ to achieve this. – Dmitry Aug 2 at 23:02
• I spent way too much time on this, you can get $O(|E||V|W)$ for integer weights where the maximum weight is $W$, and you can do a bit better if you allow approximate algorithms. Both are using decremental/incremental single-source shortest path algorithms, so you can't really expect more fruitful stuff to come from that direction. – orlp Aug 3 at 3:34
• This problem can't be solved in $O(|E|^{2- \varepsilon})$ under a widely used conjecture (k-Cycle Hypothesis). The $k$-Cycle Hypothesis can be stated in the following way. For a fixed positive integer $k$ consider the problem $k$-Cycle: detect whether there is a cycle with length exactly $k$ in the given directed unweighted graph. Then, the $k$-Cycle Hypothesis states that, for any $\varepsilon > 0$, there exists a fixed integer $k$, such that there is no algorithm that solves $k$-Cycle in $O(|E|^{2 - \varepsilon})$ time. – Kaban-5 Aug 3 at 15:33
• Now, let's reduce $k$-Cycle instance $(V, E, k)$ to our problem. We will construct a DAG with $(k + 1) |V| + 2$ vertices and $k |E| + 2|V|$ edges. The vertex set will consist of a source vertex $t$, a sink vertex $t$ and vertices $(v, \ell)$ for each $v \in V$, $\ell \in [1, k + 1]$ ($k + 1$ layers, each being a copy of $V$). There will be edges $(v, \ell) \to (u, \ell + 1)$ for all $(v, u) \in E$, $\ell \in [1, k]$ with $p = w = 0$, edges $(s, v)$ for every $v \in V$ with $w = v, e = 3|V| - 2v$ and edges $(v, t)$ with $w = v, e = 3|V| - 2v$. – Kaban-5 Aug 3 at 15:40
• @Dmitry: I meant that, for each edge in the original graph, we create $k$ copies of said edge with their $w$ and $p$ parameters being equal to $0$ (so a path of length $k$ in the original graph corresponds to a path from the first layer to the last layer). Moreover, we add $|V|$ edges from $s$ to the first layer and $|V|$ edges from the last layer to $t$, $s \to t$ paths in the new graph correspond to paths of length $k$ in the original graph. Finally, we need to choose parameters $w$ and $p$ for those "$s \to$ first layer", "last layer $\to t$" edges. – Kaban-5 Aug 3 at 17:47