Considering the bounded-degree graph model, we show that if the degree bound is two, then every graph property can be tested within query complexity that only depends on the proximity parameter. Specifically, the query complexity is \(\textrm{poly}(1/\epsilon )\) , where \(\epsilon \) denotes the proximity parameter. The key observation is that a graph of maximum degree two consists of a collection of paths and cycles, and that a collection of long paths and long cycles is relatively close (in this model) to a single cycle.

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

Testing in the Bounded-Degree Graph Model with Degree Bound Two

  • Oded Goldreich,
  • Laliv Tauber

摘要

Considering the bounded-degree graph model, we show that if the degree bound is two, then every graph property can be tested within query complexity that only depends on the proximity parameter. Specifically, the query complexity is \(\textrm{poly}(1/\epsilon )\) , where \(\epsilon \) denotes the proximity parameter. The key observation is that a graph of maximum degree two consists of a collection of paths and cycles, and that a collection of long paths and long cycles is relatively close (in this model) to a single cycle.