## On Testing Hamiltonicity in the Bounded Degree Graph Model

#### Webpage for a paper by Oded Goldreich

#### Abstract

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.