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 #2 to TR18-045 | 22nd June 2020 05:38

The Subgraph Testing Model

RSS-Feed




Revision #2
Authors: Oded Goldreich, Dana Ron
Accepted on: 22nd June 2020 05:38
Downloads: 13
Keywords: 


Abstract:

We initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph.
The tester is given free access to a base graph $G=([\n],E)$, and oracle access to a function $f:E\to\{0,1\}$ that represents a subgraph of $G$.
The tester is required to distinguish between subgraphs that posses a predetermined property and subgraphs that are far from possessing this property.

We focus on bounded-degree base graphs and on the relation between testing graph properties in the subgraph model and testing the same properties in the bounded-degree graph model.
We identify cases in which testing is significantly easier in one model than in the other as well as cases in which testing has approximately the same complexity in both models.
Our proofs are based on the design and analysis of efficient testers and on the establishment of query-complexity lower bounds.



Changes to previous version:

Correcting various minor errors and adding some clarifications.


Revision #1 to TR18-045 | 12th February 2020 18:35

The Subgraph Testing Model





Revision #1
Authors: Oded Goldreich, Dana Ron
Accepted on: 12th February 2020 18:35
Downloads: 48
Keywords: 


Abstract:

We initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph.
The tester is given free access to a base graph $G=([\n],E)$, and oracle access to a function $f:E\to\{0,1\}$ that represents a subgraph of $G$.
The tester is required to distinguish between subgraphs that posses a predetermined property and subgraphs that are far from possessing this property.

We focus on bounded-degree base graphs and on the relation between testing graph properties in the subgraph model and testing the same properties in the bounded-degree graph model.
We identify cases in which testing is significantly easier in one model than in the other as well as cases in which testing has approximately the same complexity in both models.
Our proofs are based on the design and analysis of efficient testers and on the establishment of query-complexity lower bounds.



Changes to previous version:

Significantly revised Sec 3.2 and the second part of Sec 4.


Paper:

TR18-045 | 6th March 2018 17:55

The Subgraph Testing Model





TR18-045
Authors: Oded Goldreich, Dana Ron
Publication: 6th March 2018 17:56
Downloads: 467
Keywords: 


Abstract:

We initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph.
The tester is given free access to a base graph $G=([\n],E)$, and oracle access to a function $f:E\to\{0,1\}$ that represents a subgraph of $G$.
The tester is required to distinguish between subgraphs that posses a predetermined property and subgraphs that are far from possessing this property.

We focus on bounded-degree base graphs and on the relation between testing graph properties in the subgraph model and testing the same properties in the bounded-degree graph model.
We identify cases in which testing is significantly easier in one model than in the other as well as cases in which testing has approximately the same complexity in both models.
Our proofs are based on the design and analysis of efficient testers and on the establishment of query-complexity lower bounds.



ISSN 1433-8092 | Imprint