<p>Chapter 10.5.1 of Oded Goldreich's <em>Introduction to Property Testing</em> (2017) discusses exactly that question. (See <a href="https://www.wisdom.weizmann.ac.il/%7Eoded/pt-intro.html" rel="nofollow noreferrer">his website</a> for an overview of the book, and (free) access to the drafts.)</p>
<p>Now, Theorem 10.15 states there are properties, for instance <em>cycle-freeness</em>, <em>subgraph-freeness</em>, and <em>degree regularity</em>, which have <span class="math-container">$O_\varepsilon(1)$</span>-query testers in the bounded-degree model, but require <span class="math-container">$\Omega(\sqrt{n})$</span> queries in the general graph model. This holds even under strong promises on both the average and maximum degree of the graph.</p>
<p>There also is a qualitatively similar gap (but quantitatively weaker) for triangle freeness, as discussed after Theorem 10.15.</p>
<hr />
<p>You may argue that even though there is a clear separation (constant vs. polynomial), this is still strongly sublinear. However, I am a little unclear on whether your notion of sublinear is the right one in this model anyways, where the size of the input is <span class="math-container">$n+|E|$</span> (which ranges between <span class="math-container">$n$</span> and <span class="math-container">$n^2$</span>).</p>

CC BY-SA 4.0
2021-09-27T19:22:12.510Z
Thanks for the comment. I am aware of that chapter, but I was asking more specifically about linear/superlinear. But I agree with your second point. I guess a more relevant question is $m^{1-c}$ instead of $n^{1-c}$.
user2316602
CC BY-SA 4.0
2021-09-22T09:03:01.937Z
2021-09-22T09:03:01.937Z
Clement C.
<p>Is there some natural property that is testable in strongly sublinear time (i.e. <span class="math-container">$O(n^{1-\epsilon})$</span> for some <span class="math-container">$\epsilon &gt; 0$</span>) in bounded-degree graphs but not in general graphs? If not such property is known, is there some good candidate? For example, is there a property testable in strongly sublinear time in bounded-degree graphs, for which no such algorithm is known for general graphs (as opposed to one where we know this is actually not possible)?</p>

<reference-request><randomized-algorithms><property-testing>
Property testable in sublinear time in bounded degree graphs but not in general graphs
user2316602
# Property testable in sublinear time in bounded degree graphs but not in general graphs

(Asked by: username_0 on 2021-09-16)

Is there some natural property that is testable in strongly sublinear time (i.e. $O(n^{1-\epsilon})$ for some $\epsilon > 0$) in bounded-degree graphs but not in general graphs? If not such property is known, is there some good candidate? For example, is there a property testable in strongly sublinear time in bounded-degree graphs, for which no such algorithm is known for general graphs (as opposed to one where we know this is actually not possible)?

**Tags:** reference-request, randomized-algorithms, property-testing

---

## 1 answers

### Answer by username_1 on 2021-09-22. Score: 2

Chapter 10.5.1 of Oded Goldreich's *Introduction to Property Testing* (2017) discusses exactly that question. (See [his website](https://www.wisdom.weizmann.ac.il/%7Eoded/pt-intro.html) for an overview of the book, and (free) access to the drafts.)

Now, Theorem 10.15 states there are properties, for instance *cycle-freeness*, *subgraph-freeness*, and *degree regularity*, which have $O\_\varepsilon(1)$-query testers in the bounded-degree model, but require $\Omega(\sqrt{n})$ queries in the general graph model. This holds even under strong promises on both the average and maximum degree of the graph.

There also is a qualitatively similar gap (but quantitatively weaker) for triangle freeness, as discussed after Theorem 10.15.

---

You may argue that even though there is a clear separation (constant vs. polynomial), this is still strongly sublinear. However, I am a little unclear on whether your notion of sublinear is the right one in this model anyways, where the size of the input is $n+|E|$ (which ranges between $n$ and $n^2$).

> **Comments:**
> **username_0**: Thanks for the comment. I am aware of that chapter, but I was asking more specifically about linear/superlinear. But I agree with your second point. I guess a more relevant question is $m^{1-c}$ instead of $n^{1-c}$.  

---

