Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-109 | 19th July 2020 18:44

On Testing Hamiltonicity in the Bounded Degree Graph Model

RSS-Feed




TR20-109
Authors: Oded Goldreich
Publication: 19th July 2020 18:45
Downloads: 114
Keywords: 


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.



ISSN 1433-8092 | Imprint