On Testing Hamiltonicity in the Bounded Degree Graph Model

Webpage for a paper by Oded Goldreich


We show that testing Hamiltonicity in the bounded-degree graph model requires a linear number of queries. This refers to both the path and the cycle versions of the problem, and similar results hold also for the directed analogues. In addition, we present an alternative proof for the known fact that testing Independent Set Size (in this model) requires a linear number of queries.

Material available on-line

Back to either Oded Goldreich's homepage or general list of papers.