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

Question

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.

Answer 1

This answer is mostly based on my earlier comments.

It is unlikely that there is an algorithm that works in $O(|E|^{2 - \varepsilon})$ time for all graphs. It is still possible that there are faster algorithms for dense graphs ($E = \Omega(V^2)$) or somehow dense graphs ($E = \Theta(V^\alpha)$ for some $\alpha > 1$), but an algorithm that works in $O(|E|^{2 - \varepsilon})$ time for sparse graphs ($E = O(V)$) would contradict so called $k$-cycle hypothesis (you can check this paper and this paper for more details on the statement and its applications to lower bounds for dynamic shortest path and other graph problems).

The reduction

I prefer to state the $k$-cycle hypothesis in the following way, which is equivalent to the way it is usually stated (for more details, see the last section):

For any $\varepsilon > 0$, there is a positive integer $k$, such that there is no $O(|E|^{2 - \varepsilon})$ algorithm for checking whether there is a closed walk of length exactly $k$ in the given directed graph.

Let's reduce the problem of finding a closed walk of length $k$ in a given directed graph $G(V,E)$ to the problem in question for a slighty larger graph. Construct a new graph $H$ ($H$ will be a DAG), whose vertex set consists of a source vertex $s$, 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$).

Each edge $u \to v$ of the original graph splits into $k$ edges in $H$: $(u, \ell) \to (v, \ell + 1)$ for each $\ell \in [1, k]$, with each of those edges having $w$ and $p$ parameters set to $0$. Also, there will be $|V|$ edges from the source to the first layer ($s \to (v, 1)$ with parameters $w := v$ and $p := 3|V| - 2v$ for each $v \in V$; here I assume that vertices of $G$ are numbered from $0$ to $|V| - 1$). Similarly, there will be $|V|$ edges from the last layer to $t$ ($(v, k + 1) \to t$ with $w := v$, $p := 3|V| - 2v$). Clearly, $H$ has $(k+1)|V| + 2$ vertices and $2|V| + k|E|$ edges.

Now, each $s \to t$ path $s \to (v_1, 1) \to (v_2, 2) \to \ldots (v_{k + 1}, k + 1) \to t$ in $H$ corresponds to a walk of length $k$ in the original graph ($G$). The corresponding walk is closed if and only if $v_1 = v_{k + 1}$. The main idea is that we have chosen the parameters $w$ and $p$ to ensure that paths with $v_1 = v_{k + 1}$ have the smallest possible cost.

Indeed, the cost of $s \to (v_1, 1) \to \ldots \to (v_{k + 1}, k + 1) \to t$ path in $H$ is $v_1 + v_{k + 1} + \max(3|V| - 2v_1, 3|V| - 2v_{k+1}) = v_1 + v_{k + 1} + 3|V| - \min(v_1, v_{k + 1}) = 3|V| + |v_1 - v_{k + 1}|$. Hence, the shortest $s \to t$ path in $H$ has cost $3|V|$ if and only if the original graph $G$ contained a closed $k$-walk. Therefore, under k-cycle hypothesis, there is no $O(|E|^{2 - \varepsilon})$ algorithm for problem in question.

Can we do better for dense graphs?

Honestly, I don't know. Proving lower bounds for dense graphs seems to be difficult, because the problem is strictly simpler that dynamic shortest paths. Hence, the only simple "vector of attack" is to try using the same methods that are used for dense graphs and hope that they will work even for the simpler problem. Maybe future answerers will be more succesful here?

As for faster algoritms, an existence of $O(VE)$ algorithm sounds plausible. The only thing that I managed to come up with is the following algorithm, whose complexity is a bit hard to estimate, but I suspect that it still should take $\Omega(E^2)$ time in the worst case:

Find some shortest ($s \to t$)-path in the original graph with respect to sum of $w$'s, breaking ties by minimizing the maximum of $p$'s (it is possible to do this by dynamic programming in $O(|E|)$ time). Let's say that the largest value of $p$ for edges on the chosen path is $P$. Then, all edges $e$ with $p_e \geqslant P$ can't appear in a path with a smaller cost (because otherwise the chosen path was not shortest with respect to sum of $w$'s). Therefore, we can delete all such edges and repeat the process.

Why did I choose an uncommon statement of k-cycle hypothesis?

Usually, it is stated in the terms of finding a simple cycle of length $k$, but for fixed $k$ finding a simple cycle can be reduced to finding a closed walk in (larger) graph by known techniques like color coding. All these techniques require blow up the size of the graph exponentially with respect to $k$ (otherwise we could solve Hamiltonian Cycle in subexponential time), but we can handle this, because $k$ is fixed and small.

Intuitively speaking, for small $k$, the "main problem", asymptotically speaking, is not ensuring that all vertices of the cycle are different, but remembering where the cycle started.

Because the problems are equivalent, I chose the one which is easier to work with. Moreover, apart from having a theoretical reduction, we also have a practical reduction now. For example, if we assume that there is no way to check whether a graph with $10^6$ edges has a closed walk of length $k = 6$ in under $10$ minutes on a normal computer (I would say, that this is a huge understatement, considering the large constant factors of graph searches; though I would be very positively surprised to be wrong), then there is no way to solve the problem in question for graphs with $10^6 / (k + 2) = 1.25 \cdot 10^5$ edges in under $10$ minutes, e.t.c. The point is, that the constant factors involved in the reduction are reasonably small.