# Property testable in sublinear time in bounded degree graphs but not in general graphs

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)?

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.
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$$).
• 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}$. Sep 27 '21 at 19:22