# \alpha-path on Euclidean graphs

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.

1. 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).

2. 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!

• You have a decision problem. I am not sure what you mean by an "approximation" algorithm. – Chandra Chekuri Sep 30 '17 at 21:16
• Like if it returns YES, then the path has length \elll where \alpha < \ell <c.\alpha for some constant c. If NO, then otherwise. We can consider the problem of reporting paths having approximate length bounded by some constant times \alpha. – Armin Mir Oct 1 '17 at 3:13