1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ You have a decision problem. I am not sure what you mean by an "approximation" algorithm. $\endgroup$ – Chandra Chekuri Sep 30 '17 at 21:16
  • $\begingroup$ 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. $\endgroup$ – Armin Mir Oct 1 '17 at 3:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.