On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs

We study property testing of (di)graph properties in bounded-degree graph models. The study of graph properties in bounded-degree models is one of the focal directions of research in property testing in the last 15 years. However, despite the many results and the extensive research effort, there is...

Full description

Saved in:
Bibliographic Details
Published in:Computational complexity 2020-06, Vol.29 (1), Article 1
Main Authors: Ito, Hiro, Khoury, Areej, Newman, Ilan
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Computational Mathematics and Numerical Analysis
Computer Science
Graph theory
Graphs
Properties (attributes)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study property testing of (di)graph properties in bounded-degree graph models. The study of graph properties in bounded-degree models is one of the focal directions of research in property testing in the last 15 years. However, despite the many results and the extensive research effort, there is no characterization of the properties that are strongly testable (i.e. testable with constant query complexity) even for 1-sided error tests. The bounded-degree model can naturally be generalized to directed graphs resulting in two models that were considered in the literature. The first contains the directed graphs in which the out-degree is bounded but the in-degree is not restricted. In the other, both the out-degree and in-degree are bounded. We give a characterization of the 1-sided error strongly testable monotone graph properties and the 1-sided error strongly testable hereditary graph properties in all the bounded-degree directed and undirected graphs models.
ISSN:1016-3328
1420-8954
DOI:10.1007/s00037-019-00191-6