2
$\begingroup$

Consider an input set of vertices $V$ and vertices $s,t\in V$. The goal is to learn some unknown shortest path from $s$ to $t$; the set of edges of the graph is hidden at first and there may be multiple shortest paths.

At each iteration, each vertex is randomly colored using $0$ or $1$. We then get a single bit, that is $1$ with a probability proportional to the number of $1$-vertices along the path. That is, if $6$ of the vertices along the path were colored with $1$ and $4$ were zero, then the bit will be $1$ w.p. 3/5.

Importantly, we get to know the coloring of every iteration, and the goal path does not change.

How many samples do we need until we can compute the path with, say, probability 2/3?


A very simplistic approach would be to eliminate all monochromatic paths whose color is different than the given bit (e.g., a $1$-path can be eliminated if we get a $0$-bit). This seems to give a very weak bound.

$\endgroup$
  • 1
    $\begingroup$ You may as well assume that the graph is just a single path (and a bunch of isolated vertices), as the other edges do not in any way affect the random process. In fact, the edges in the path also do not affect the random process; the path just acts as a subset of $V$. $\endgroup$ – Emil Jeřábek May 28 at 16:46
4
$\begingroup$

Here’s a simple idea: try a certain number $s$ of samples, and for each vertex, record how many times its colour agreed with the provided bit.

For vertices outside the path, they agree with probability $1/2$ on each iteration, while for vertices on the path, the probability is $1/2+1/2k$, where $k$ is the number of vertices on the path.

Thus, if $s\approx k^2\log n$, the Chernoff–Hoeffding inequality ensures that with probability at least $2/3$, all vertices outside the path agree for less than $s(1/2+1/4k)$ samples, and all vertices on the path agree for more than $s(1/2+1/4k)$ samples, which lets you pinpoint the path. If you don’t know $k$ in advance, you can just bound it by $n$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.