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.

Feb 2021: We just found out that the main result has been proved by Yuichi Yoshida and Hiro Ito more than a decade ago.

Material available on-line

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