Tag: Types

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.