The locality of finding a path in a graph

We examine theoretical bounds on the locality of finding a path
between two given nodes in a graph. A local forwarding algorithm A at
a vertex v receives a message P and selects one of its neighbours to
which to forward P using only local information. Specifically, in
addition to knowing the node for which P is destined, algorithm A may
also know the node from which P originated, the neighbour from which
node v received P, and the subgraph corresponding to all nodes within
distance k of node v. Our objective is to determine which of these
parameters are necessary and/or sufficient to permit successful
message delivery as k varies. We establish tight bounds on k for the
feasibility of deterministic k-local path finding for various
combinations of these parameters. Although motivated by applications
in networks, this work consists of combinatorial and graph-theoretic
arguments.

This is joint work with Prosenjit Bose and Paz Carmi.