License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.37
URN: urn:nbn:de:0030-drops-101308
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10130/
Go to the corresponding LIPIcs Volume Portal

Goldreich, Oded ; Ron, Dana

The Subgraph Testing Model

pdf-format:
LIPIcs-ITCS-2019-37.pdf (0.4 MB)

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 -> {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.

BibTeX - Entry

@InProceedings{goldreich_et_al:LIPIcs:2018:10130,
  author =	{Oded Goldreich and Dana Ron},
  title =	{{The Subgraph Testing Model}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{37:1--37:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10130},
  URN =		{urn:nbn:de:0030-drops-101308},
  doi =		{10.4230/LIPIcs.ITCS.2019.37},
  annote =	{Keywords: Property Testing, Graph Properties}
}

Keywords: Property Testing, Graph Properties
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI