ECCC-Report TR20-109https://eccc.weizmann.ac.il/report/2020/109Comments and Revisions published for TR20-109en-usTue, 09 Feb 2021 19:13:04 +0200
Revision 2
| On Testing Hamiltonicity in the Bounded Degree Graph Model |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2020/109#revision2We 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.
Tue, 09 Feb 2021 19:13:04 +0200https://eccc.weizmann.ac.il/report/2020/109#revision2
Revision 1
| On Testing Hamiltonicity in the Bounded Degree Graph Model |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2020/109#revision1We 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.
Tue, 09 Feb 2021 19:10:33 +0200https://eccc.weizmann.ac.il/report/2020/109#revision1
Paper TR20-109
| On Testing Hamiltonicity in the Bounded Degree Graph Model |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2020/109We 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.
Sun, 19 Jul 2020 18:45:33 +0300https://eccc.weizmann.ac.il/report/2020/109