Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR20-109 | 9th February 2021 19:13

On Testing Hamiltonicity in the Bounded Degree Graph Model

RSS-Feed




Revision #2
Authors: Oded Goldreich
Accepted on: 9th February 2021 19:13
Downloads: 63
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.



Changes to previous version:

Uploaded the wrong file...


Revision #1 to TR20-109 | 9th February 2021 19:10

On Testing Hamiltonicity in the Bounded Degree Graph Model





Revision #1
Authors: Oded Goldreich
Accepted on: 9th February 2021 19:10
Downloads: 58
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.



Changes to previous version:

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


Paper:

TR20-109 | 19th July 2020 18:44

On Testing Hamiltonicity in the Bounded Degree Graph Model





TR20-109
Authors: Oded Goldreich
Publication: 19th July 2020 18:45
Downloads: 283
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