The problem
Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$.
Assumptions about the graph: You may assume that $G$ is a random graph of the type $G(n,p)$. The truth is that I work with some kind of small-world graph, however I don't know how to model its characteristics with respect to this question. Sorry :(
We define the graph metric $d$ for every two vertices $x,y$ to be $d(x,y)$: The length of shortest path between $x$ and $y$.
For every $a,b \in T$, $d(a,b)$ is known. This is called the "global knowledge". Also for every $x \in V, a \in T$, the distance $d(x,a)$ is known. $A(x)$ is also known from $x$. This is called the "local knowledge" for the vertex $x$.
For a vertex $x \in V$, The address of $x$, $A(x)$, is a set of shortest paths from $x$ to all the vertices in $T$.
A person should travel from $x$ to $y$. This is done by hopping from one vertex to one of its neighbours.
Information given:
- $A(y)$
- The global knowledge
- While staying at the vertex $z$, the local knowledge with respect to $z$ is known.
Find an algorithm to travel from $x$ to $y$. (It might be a probabilistic one). The following properties are required:
- The total length of the journey from $x$ to $y$ should not be more than $\log(|V|)\cdot d(x,y)$
- Assume that use the proposed algorithm to send $R$ people between random pairs $x,y \in V$. Let $J(x)$ be the amount of journeys passing through $x$. Then $J(x) \leq J(y)\cdot\log(|V|)$ with high probability when $R \rightarrow \infty$.
My attempts
I tried a few things, though I didn't have much progress. If you have any kind of idea, please post it.
Naive solution
The naive solution to go from $x$ to $y$ would be to use an intermediate vertex $t \in T$: First we travel from $x$ to $t$, and then as we know $A(y)$, we could follow a shortest path from $t$ to $y$.
This generally works, however the load on the vertices of $T$ will be too high, which means that the second requirement from the algorithm will not be satisfied.
Metric information
Using the basic properties of metrics, we can conclude the following: $\max_{a \in T} \left|d(a,y) - d(x,a)\right| \leq d(x,y) \leq \min_{a \in T}\left(d(x,a) + d(a,y)\right)$
This could give us some kind of approximation to how far we are from $y$ at any point of the journey, but this approximation is usually not so good.
Continuity
We can look at the distances from a vertex $z$ to all vertices of $T$ as a set of coordinates, in some sense.
When hopping from a vertex $z$ to his neighbour $w$, one can prove that the distance to each of the vertices inside $T$ will change only by $+1$, $-1$ or $0$.
Therefore the coordinates are somehow continuous with respect to hopping to your neighbour. I didn't manage to get further with this idea, but it is kind of interesting.
Embedding
If we manage to embed the graph in an euclidean space (Maybe of high dimension) so that all distances are preserved, we could use euclidean distance and have some better understanding of the geometry of the graph. Just an idea. I never managed to do anything of this sort.
The Random aspect
It seems like this not problem is not solvable in the "exact" sense, as it is possible to have two different vertices with the same set of "coordinates" on some specially crafted graph. (In that case, The Address of a vertex does not really define it). However I think that the probability of getting this kind of special graph is very low.
