Consider the following problem:
Suppose we are given a G=(V, E) Euclidean Graph in the plane and a real $\alpha > 0$. For simplicity assume, there exists only one path whose summation of weights over all edges is equal to \alpha. Give a polynomial decider to report such a \alpha-path in G if exists.
In spite of the fact that there are several experimental results (heuristic algorithm) for this problem I know there are several randomized algorithms have been given by people using color-coding in running times O(2^k. poly(n)) [Williams] and O((1.625)^k.poly(n)) [Abbasi et al.], etc. for the case that graph is Unweighted, Non-geometric and integer k is considered as the number of vertices on the target path. The question is, is there any approximation algorithm for either on Euclidean or general graph or not? ( I know \alpha or k can be large to extract the longest path, but here the length of longest path is given and might not be as hard as longest path problem).
I am trying to come up with a preliminary solution for the Euclidean case using a hierarchical structure like quadtree or something to store the length of each subpath hierarchically into some higher level node(s) of the tree. Finding K=O(log \phi) nodes in the tree that gives us c.\alpha-path or some c, can tell us about the existence of a path on original graph. Can anyone give me some feedback about this approach? Or do I need using another different data structure? Any comment in regard to this problem is appreciated!
