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

  • 1
    $\begingroup$ Do you mean "conjectured to be EXPTIME-complete"? Membership in EXPTIME seems pretty easy: Enumerate all simple paths by brute force. $\endgroup$
    – Jeffε
    Apr 28, 2012 at 13:59
  • $\begingroup$ Well, the authors refer just to EXPTIME but you are definitely right and that is trivial. I guess they meant EXPTIME-complete $\endgroup$ Apr 28, 2012 at 21:32


Browse other questions tagged or ask your own question.