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.

Improve this question
$\endgroup$
4
  • 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
    Commented May 2, 2012 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
    Commented May 2, 2012 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
    Commented Sep 6, 2015 at 15:18
  • $\begingroup$ ouch! sorry about that David! I'll try to take care with that! $\endgroup$
    – Carlos Linares López
    Commented Sep 6, 2015 at 23:49

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Some detail (e.g. algorithm ideas) would be nice, though. $\endgroup$
    – Raphael
    Commented Oct 8, 2012 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
    Commented Oct 9, 2012 at 6:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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