<p>Consider the following problem:</p>

<ul>
<li><p>Suppose we are given a G=(V, E) Euclidean Graph in the plane and a real $\alpha &gt; 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.</p>

<ol>
<li><p>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 <em>Unweighted</em>, <em>Non-geometric</em> 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). </p></li>
<li><p>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!</p></li>
</ol></li>
</ul>

CC BY-SA 3.0
2017-09-30T21:16:17.593Z
You have a decision problem. I am not sure what you mean by an "approximation" algorithm.
Chandra Chekuri
CC BY-SA 3.0
2017-10-01T03:13:20.657Z
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
<ds.algorithms><graph-algorithms><approximation-algorithms><ds.data-structures><lower-bounds>
\alpha-path on Euclidean graphs
Armin Mir
# \alpha-path on Euclidean graphs

(Asked by: username_0 on 2017-09-30)

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!

**Tags:** ds.algorithms, graph-algorithms, approximation-algorithms, ds.data-structures, lower-bounds
> **Comments:**
> **username_1**: You have a decision problem. I am not sure what you mean by an "approximation" algorithm.  
> **username_0**: 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.  

---

## 0 answers

