10
$\begingroup$

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.

| cite | improve this question | |
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.
$\endgroup$
  • 2
    $\begingroup$ @BernardoSubercaseaux, you can add a constant to all $p(e)$ to achieve this. $\endgroup$ – Dmitry Aug 2 at 23:02
  • 1
    $\begingroup$ 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. $\endgroup$ – orlp Aug 3 at 3:34
  • 2
    $\begingroup$ 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. $\endgroup$ – Kaban-5 Aug 3 at 15:33
  • 1
    $\begingroup$ 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$. $\endgroup$ – Kaban-5 Aug 3 at 15:40
  • 2
    $\begingroup$ @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. $\endgroup$ – Kaban-5 Aug 3 at 17:47

Your Answer

Miel Sharf is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.