Upper and lower bounds for the average-case complexity of path-search

A channel graph is the union of all paths between a given input and a given output in an interconnection network. At any moment in time, each vertex in such a graph is either idle or busy. The search problem that we consider is to find a path (from the given input to the given output) consisting entirely of idle vertices or to find a cut (separating the given input from the given output) consisting entirely of busy vertices. We shall also allow the search to fail to find either a path or a cut with some probability bounded by a parameter called the failure probability. This is to be accomplished by sequentially probing the idle-or-busy status of vertices, where the vertex chosen for each probe may depend on the outcome of previous probes. Thus, a search algorithm may be modeled as a decision tree. For average-case analysis, we assume that each vertex is independently idle with some fixed probability, called the vacancy probability (and therefore busy with the complementary probability). For one commonly studied channel graph type, the parallel graph, we show that the expected number of probes is at most proportional to the length of a path, irrespective of the vacancy probability, and even if the allowed failure probability is zero. Another type of channel graph that we study is the spider-web graph, which is superior to the parallel graph as regards linking probability (the probability that an idle path, rather than a busy cut, exists). For this graph, we give upper and lower bounds that grow exponentially with the length of a path, when the vacancy probability and failure probability are fixed appropriately.