TR05-073 Authors: Oded Goldreich, Dana Ron

Publication: 14th July 2005 14:07

Downloads: 1886

Keywords:

Inspired by Feige ({\em 36th STOC}, 2004),

we initiate a study of sublinear randomized algorithms

for approximating average parameters of a graph.

Specifically, we consider the average degree of a graph

and the average distance between pairs of vertices in a graph.

Since our focus is on sublinear algorithms, these algorithms

access the input graph via queries to an adequate oracle.

We consider two types of queries.

The first type is standard neighborhood queries

(i.e., {\em what is the $i^\xth$ neighbor of vertex $v$?}),

whereas the second type are queries regarding the quantities

that we need to find the average of

(i.e., {\em what is the degree of vertex $v$?}\/

and {\em what is the distance between $u$ and $v$?},

respectively).

Loosely speaking, our results indicate a difference between the

two problems: For approximating the average degree,

the standard neighbor queries suffice and in fact are preferable

to degree queries. In contrast, for approximating average distances,

the standard neighbor queries are of little help whereas distance

queries are crucial.