3
$\begingroup$

Suppose I am inside a finite, weighted cubic graph without loops, with no information regarding its layout, including the number of vertices or distances to the adjacent vertices. I want to reach a target vertex, but I will only know where it is once I reach it.

  1. Assuming that the bottleneck on search time depends not on computation but only on the distance travelled within the graph itself whilst searching, what is the asymptotically fastest algorithm for reaching the target? My guess is that it'll still be a version of Dijkstra's for sparse graphs, modified to take into account the limited information available - but I have little intuition for this area and could be completely wrong.

  2. Given this algorithm, what is a family of cubic graphs (ordered by number of vertices) on which the algorithm performs badly, in the sense that the ratio of mean square search time to mean square shortest path across all ordered pairs of vertices is high (when compared with other cubic graphs on the same number of vertices)?

Added for clarity, per the comments below:

  • I can recognize a vertex once I've visited it, so that if I later return to it via a different path I will know where I am.
  • If I am at one end of an edge that I have previously only seen the opposite end of, I can not recognize it.
  • I will allow algorithms to turn around partway along an edge and return to the previous vertex in order to choose a different edge.
Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ arxiv.org/abs/quant-ph/0209131 $\endgroup$
    – Steve Huntsman
    Commented Jul 28, 2011 at 0:51
  • $\begingroup$ Once you reach both of them, can you tell whether or not the $m$-th vertex you reached is the same as the $n$-th vertex you reached? Can you tell whether two edge parts you've seen are part of the same edge? Do you restrict to simple graphs? $\endgroup$
    – user5810
    Commented Jul 28, 2011 at 0:57
  • $\begingroup$ This sounds like the cow-path problem. A linear version is as follows: a robot can traverse a number line back and forth to find an apple placed on it somewhere. What are upper and lower bounds on the number of (unit distance) steps needed to find the apple given the apple is $n$ units away (although the robot does not know $n$ or even if it is in the plus or minus direction). If I am right in guessing this is a similar problem, the answer is something like 9n. Gerhard "Walking And Searching For Similarities" Paseman, 2011.07.27 $\endgroup$
    – Gerhard Paseman
    Commented Jul 28, 2011 at 0:57
  • $\begingroup$ Oops, I mean $9n$ for the linear version. For the branched version, it will again be an O(n) algorithm with the constant not too large, if you are allowed to remember what branches you finished. Gerhard "Ask Me About System Design" Paseman, 2011.07.27 $\endgroup$
    – Gerhard Paseman
    Commented Jul 28, 2011 at 1:00
  • $\begingroup$ @Ricky: I am restricting to simple graphs, and assuming that vertices can be recognized once they have been reached but edges can not be recognized from one end if they have only been seen from the opposite end. @Steve: I can see how that problem is related, but I am not sure to what extent. In particular, the graphs described in that paper have a very specific structure (in fact, they are technically not cubic), which seems to be key to the algorithms considered. $\endgroup$
    – Robin Saunders
    Commented Jul 28, 2011 at 1:40

2 Answers 2

Reset to default
1
$\begingroup$

With respect to your question about on which graphs the algorithms performs poorly, have you considered expanders? Expanders look locally tree-like, which means that the number of vertices at distance $d$ from your starting vertex is exponential in $d$ (at least as long as the ball of radius $d$ around the start vertex has less than half the graph). Thus, even if your algorithm visits vertices in an ideal order, it should take exponentially longer than following the shortest path.

Improve this answer
$\endgroup$
1
$\begingroup$

Since you used the word "travelled", I am guessing you want a traversal-based type of algorithm. If you have other means of searching the graph, you should make it clear.

This really sounds to me like a cow-path problem. However, you might try search games to see if other algorithms like those for the Chinese postman problem are more suitable for your problem. If you do a web search on cow-path, you will find a randomized algorithm where the expected runtime is (a real number which is) about 7 times the distance from the goal.

Gerhard "Ask Me About System Design" Paseman, 2011.07.27

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ok, and thanks for the link on search games. However, I'm guessing the structure of the graph makes some difference? The real goal of the question, as the title implies, was to find some graphs where the algorithm (whatever the exact details of its nature) performs poorly. $\endgroup$
    – Robin Saunders
    Commented Jul 28, 2011 at 10:21
  • $\begingroup$ Except for the fact that you say cubicc graphs, I would suggest star graphs or wheel graphs as examples that are hardest to navigate. Perhaps a cubic approximation to a star? Gerhard "Twinkle, Twinkle, Big Cubic Graph" Paseman, 2011.07.28 $\endgroup$
    – Gerhard Paseman
    Commented Jul 28, 2011 at 15:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .