2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

Chapter 10.5.1 of Oded Goldreich's Introduction to Property Testing (2017) discusses exactly that question. (See his website 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$).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.