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.

Uploaded the wrong file...

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.

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

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.