1
$\begingroup$

I've got the following problem

Consider a DAG $G=(V,E)$ with $V=[v_1,…,v_n]$, and edge-set $E=[e_1,…,e_m]$, with associated costs $c_1,…,c_m$. The problem is to find the shortest paths from an initial vertex $s$ to multiple targets $t_1,…,t_k$, taking into account these costs. A typical shortest path problem.

However, my problem is slightly different: the costs $c_1,…,c_m$ depend on the previously traversed nodes Is there an alternative to the brute-force solution: find all the simple paths between $s$ and $t$ and then select the one with the lowest cost?

Path can be compared. Take as example the following graph: Red arcs are "checkpoint arcs". All the sub-paths having a red arc as last one can be compared, so a local decision can be taken. Similarly, costs are reset after traversing such arcs: 22->23 has a different cost if the subpath includes the arc 11->22 or not.

enter image description here

EDIT 2:

Costs are related to two sequences: $P$ and $Q$, where $len(P)=N$ and $len(Q)=M$. In the aforementioned case $M=N=4$. Each element of $P$ and $Q$ is a tuple $(t,p)$. The tuple ($t_i,p_i)$ is the ith tuple of the sequence. Tuples are constrained on $t$: $t_{i+1} > t_i$. There's no constraint on $p$.

Let $s_p$ a set of valid indices for the sequence $P$ and $s_qp$ a set of valid indices for the sequence $Q$. The cost $C(s_p,s_q)= C_t(s_p,s_q)+C_q(s_p,s_q)$ where $C_t = max(max(P[s_p][t]),max(Q[s_q][t])) - min(min(P[s_p][t]),min(Q[s_q][t]))$ and $C_p = max(max(P[s_p][p]),max(Q[s_q][p])) - min(min(P[s_p][p]),min(Q[s_q][p]))$

The cost $C(s_p,s_q)$ represents the "diameter" of the element obtained by merging the $s_p$th elements of $P$ and the $s_q$th elements of $Q$.

Each path in the graph builds different $s_p$ and $s_q$ sets. For example, the path 00,11,22,33 has a cost $C_{tot} = C(0,0)+ C(1,1)+ C(2,2)+ C(3,3)$, while the path 00 - 01 - 12 - 22 - 33 has a cost $C_{tot} = C(0,[0,1])+ C([1,2],2)+ C(3,3)$

$\endgroup$
  • 3
    $\begingroup$ Do the costs depend on all previously traversed nodes (so there are an exponential number of potential costs)? If so, how are they given? $\endgroup$ – SamM May 16 '15 at 17:26
  • 1
    $\begingroup$ Your question as stated is not answerable. The only useful answer is "It depends". It depends on how the cost of the path is defined. There are some cost functions where you can't do any better than enumerating all paths; and others where you can do vastly better. So, please edit the question to specify this necessary information. $\endgroup$ – D.W. May 18 '15 at 19:38
  • $\begingroup$ I edited the question adding the needed information $\endgroup$ – Felipe Rojas May 19 '15 at 9:26
  • $\begingroup$ Thanks for the added info. It seems that one of the sets $s_p$ and $s_q$ is always a contiguous sequence of indices while the other is a singleton. So you can easily compute all $C(i,[j,...,k])$ as well as $C([i,...,j],k)$. From there, you can compute the shortest path in $O(nm(n+m))$ time. However, using dynamic programming, I think you can actually compute the minimum $C_{tot}$ in $O((n+m)^2)$ time. $\endgroup$ – Tim May 19 '15 at 22:35
  • 1
    $\begingroup$ I see what you mean now. In that case the naive dynamic programming approach would be using a 6-dimensional table $(x,y,\min_p,\max_p,\min_t,\max_t)$, storing the cost of the minimum path to node $(x,y)$, such that the minima and maxima since the last checkpoint are $(\min_p,\max_p,\min_t,\max_t)$. Since there are $m+n$ candidate values for each minimum and maximum, this table may be huge, but at least gives a polynomial time algorithm. There may be more efficient ways though. $\endgroup$ – Tim May 20 '15 at 17:25
6
$\begingroup$

Without further information on how the costs can vary, the problem is NP-complete. For instance, consider the following rule for setting costs:

  • If an edge would return to a previously-traversed node then its cost is $n$
  • If an edge reaches $t$ without previously traversing all other nodes then its cost is $n$
  • In all other cases the cost of an edge is $1$.

For such a rule, a Hamiltonian path has cost $n-1$ and all other paths have cost $n$ or greater. The problem could still be solved more efficiently than a brute-force search (e.g. in time $O(n^22^n)$ by dynamic programming) but not in polynomial time unless $\mathsf{P}=\mathsf{NP}$.

So if you want to find a polynomial time algorithm you will need to be much more specific about what sort of dependence between edge cost and previous path information is allowed.

$\endgroup$
  • $\begingroup$ The underlying digraph is acyclic, which makes the Hamiltonian path problem tractable. $\endgroup$ – Gamow May 18 '15 at 16:47
  • 2
    $\begingroup$ Good point. But all that means is that we have to use the same costs on a DAG that has $n$ copies of each vertex, and that replaces each edge $uv$ in a hard instance of Hamiltonian paths with $n-1$ edges $u_iv_{i+1}$ between copies of the same vertices in the expanded DAG. $\endgroup$ – David Eppstein May 18 '15 at 18:25
  • $\begingroup$ Why the path has to be hamiltonian? $\endgroup$ – Felipe Rojas May 19 '15 at 9:26
  • $\begingroup$ Because any other path would be longer. $\endgroup$ – David Eppstein May 19 '15 at 16:34
0
$\begingroup$

Although this question does not seem research-level, here is a solution that does not check all possible paths (elaborating on the above comment).

The naive dynamic programming approach is to use a 6-dimensional table $(x,y,min_p,max_p,min_t,max_t)$, storing the cost of the minimum path to node $(x,y)$, such that the minima and maxima since the last checkpoint are $(min_p,max_p,min_t,max_t)$.

Since there are $m+n$ candidate values for each minimum and maximum, this table may be huge, namely size $O(m\cdot n\cdot (m+n)^4)$. You can implement this using a hash-table, mapping each $(x,y,min_p,max_p,min_t,max_t)$.

// T[x,y,min_p,max_p,min_t,max_t] will eventually contain:
// the minimum cost of a path (excluding the cost since the last checkpoint) to node (x,y)
// such that the minimum P.p or Q.p since the last checkpoint of that path is min_p, etc.
T = empty hash table
for x in [0..m-1]
  for y in [0..n-1]
    for min_p in P.ps + Q.ps
      for max_p in P.ps + Q.ps
        for min_t in P.ts + Q.ts
          for max_t in P.ts + Q.ts
            T[x,y,min_p,max_p,min_t,max_t] = infinity
// there is only one path to (0,0)
// if we don't count the cost since the last checkpoint, this path has cost 0
T[0,0,min(P[0].p,Q[0].p),max(P[0].p,Q[0].p),...] = 0
for x in [0..m-1]
  for y in [0..n-1]
    for min_p in P.ps + Q.ps
      for max_p in P.ps + Q.ps
        for min_t in P.ts + Q.ts
          for max_t in P.ts + Q.ts
            cost_to_xy = T[x,y,min_p,max_p,min_t,max_t]
            // try advance P
            if x<m-1
              key = (x+1,y,min(min_p,P[x+1].p),max(max_p,P[x+1].p),...)
              T[key] = min(T[key], cost_to_xy)
            // try advance Q
            if y<n-1
              key = (x,y+1,min(min_p,Q[y+1].p),max(max_p,Q[y+1].p),...)
              T[key] = min(T[key], cost_to_xy)
            // try advance both (checkpoint)
            if x<m-1 and y<n-1
              key = (x+1,y+1,min(P[x+1].p,Q[y+1].p),max(P[x+1].p,Q[y+1].p),...)
              T[key] = min(T[key], cost_to_xy + max_t-min_t + max_p-min_p)

The cost of the optimal path is then the minimum over all $T[m-1,n-1,min_p,max_p,min_t,max_t] + max_t - min_t + max_p - min_p$

Disclaimer: This solution is not at all optimized and you still have to fill some blanks. Neither does it give you the actual path, but you can get it with some small tweaks.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.