6
$\begingroup$

[previously appearing in cstheory, it was closed there and introduced here instead]

Given an edge-weighted graph $G=(V,E)$ the problem of finding the shortest path is known to be in P ---and indeed a simple approach would be Dijkstra's algorithm which can solve this problem in $O(V^2)$. A similar problem is to find the maximum path in $G$ from a source node to a target node and this can be solved with Integer Programming so that, as far as I know, this is not known to be in P.

Now, the problem of finding a path in $G$ such that it deviates the minimum from a given target value (typically larger than the optimal distance but less than the maximum distance that separates the source and target nodes) has been conjectured to be in EXPTIME (see section "Conventions" of A depth-first approach to target-value search in the proceedings of SoCS 2009). In particular, this paper addresses this particular problem for directed acyclic graphs (DAGs). A previous work is Heuristic Search for Target-Value Path Problem. There is event a US Patent of this algorithm US 2011/0004625.

I've been searching for related problems in other fields of Computer Science and Mathematics and strikingly, I have found none though this problem is clearly relevant in practice ---there are tons of opportunities to look for a specific target value instead of the minimum or the maximum path.

Do you know related problems to this or additional bibliographical references to this problem? Any information on this problem including studies of their complexity would be very welcome

Note: as already pointed out by Jeffe in cstheory, proving this problem to be in EXPTIME is trivial and the authors probably meant EXPTIME-complete.

$\endgroup$
  • 6
    $\begingroup$ In the case of DAG, all paths can be enumerated in polynomial space and therefore the problem cannot be EXPTIME-complete unless PSPACE=EXPTIME. The natural decision version (given a DAG G, its vertices s and t, and numbers x and y, decide whether there is a path from s to t whose length is between x and y) is in NP. $\endgroup$ – Tsuyoshi Ito May 2 '12 at 13:19
  • $\begingroup$ Wou Tsuyoshi! This is a very value response! Would you mind to post it as an aswer? I would happily up vote it. $\endgroup$ – Carlos Linares López May 2 '12 at 13:55
  • $\begingroup$ Hi, Carlos. I notice that you've been approving quite a lot of edits to posts that are several years old, when those edits do nothing more than improve a certain author's use of capital letters. Please don't do that: accepting these edits brings the old question back onto the front page of the site, which means that recent, active questions get pushed onto the second page, where people don't see them. The issues are similar to the ones raise here. Accepting these edits does more harm than good. Cheers. $\endgroup$ – David Richerby Sep 6 '15 at 15:18
  • $\begingroup$ ouch! sorry about that David! I'll try to take care with that! $\endgroup$ – Carlos Linares López Sep 6 '15 at 23:49
4
$\begingroup$

What follows is taken from Tsuyoshi Ito's comment.

In the case of DAG, all paths can be enumerated in polynomial space and therefore the problem cannot be EXPTIME-complete unless PSPACE=EXPTIME. The natural decision version (given a DAG G, its vertices s and t, and numbers x and y, decide whether there is a path from s to t whose length is between x and y) is in NP.

$\endgroup$
  • $\begingroup$ Some detail (e.g. algorithm ideas) would be nice, though. $\endgroup$ – Raphael Oct 8 '12 at 20:17
  • $\begingroup$ Thanks a lot for putting the comment into an answer! One caveat however: could anyone extend these results for the case of undirected graphs where cycles are allowed? In this particular case, one can think of two variants of the same problem: i) nodes cannot be revisited; ii) edges cannot be traversed more than once. $\endgroup$ – Carlos Linares López Oct 9 '12 at 6:25

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.