Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-047 | 13th March 2024 17:32

On the query complexity of testing local graph properties in the bounded-degree graph model

RSS-Feed




Revision #1
Authors: Oded Goldreich
Accepted on: 13th March 2024 17:32
Downloads: 50
Keywords: 


Abstract:

We consider the query complexity of testing local graph properties in the bounded-degree graph model.
A local property is defined in terms of forbidden subgraphs that are augmented by degree information, where the latter account also for neighbors that are not in the subgraph.
Indeed, this formulation yields a generalized notion of subgraph-freeness, which extends the standard notions of induced and non-induced subgraph freeness.

While it is tempting to conjecture that every local graph property has a constant-query proximity-oblivious tester(in the bounded-degree graph testing model), this conjecture was refuted by Adler, Kohler and Peng (32nd SODA and 36th CCC, 2021).
In fact, they showed that there exist local graph properties that cannot be tested (in this model) within a number of queries that does not depend on the size of the graph.
However, their proof gives no explicit lower bound on the dependence of the query complexity on the size of the graph.

In this paper, we provide such an explicit bound.
This is done by studying the query complexity of the specific local graph property presented by Adler et al.
In a natural (but not standard) model, in which the tester is not given the size of the graph but rather only a rough approximation of this size, this property has logarithmic (in the graph's size) query complexity.
In the standard model, we only obtain a quadruple-logarithmic lower bound.



Changes to previous version:

minor revision: fixing some minor errors etc


Paper:

TR24-047 | 8th March 2024 13:39

On the query complexity of testing local graph properties in the bounded-degree graph model





TR24-047
Authors: Oded Goldreich
Publication: 8th March 2024 13:39
Downloads: 93
Keywords: 


Abstract:

We consider the query complexity of testing local graph properties in the bounded-degree graph model.
A local property is defined in terms of forbidden subgraphs that are augmented by degree information, where the latter account also for neighbors that are not in the subgraph.
Indeed, this formulation yields a generalized notion of subgraph-freeness, which extends the standard notions of induced and non-induced subgraph freeness.

While it is tempting to conjecture that every local graph property has a constant-query proximity-oblivious tester(in the bounded-degree graph testing model), this conjecture was refuted by Adler, Kohler and Peng (32nd SODA and 36th CCC, 2021).
In fact, they showed that there exist local graph properties that cannot be tested (in this model) within a number of queries that does not depend on the size of the graph.
However, their proof gives no explicit lower bound on the dependence of the query complexity on the size of the graph.

In this paper, we provide such an explicit bound.
This is done by studying the query complexity of the specific local graph property presented by Adler et al.
In a natural (but not standard) model, in which the tester is not given the size of the graph but rather only a rough approximation of this size, this property has logarithmic (in the graph's size) query complexity.
In the standard model, we only obtain a quadruple-logarithmic lower bound.



ISSN 1433-8092 | Imprint