Scholarlink

We present a proof of the fact 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. These results were established before by Yoshida and Ito (IEICE Trans. Inf. Syst., Vol. 93-D (2), 2010). Our proof is similar in its high-level strategy, but different in some of its details. 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.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On Testing Hamiltonicity in the Bounded Degree Graph Model

  • 章节

  • 发表日期：

    2025年

查看全文
  • Oded Goldreich

摘要

We present a proof of the fact 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. These results were established before by Yoshida and Ito (IEICE Trans. Inf. Syst., Vol. 93-D (2), 2010). Our proof is similar in its high-level strategy, but different in some of its details. 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.