The Library
A characterization of graph properties testable for general planar graphs with one-sided error (it's all about forbidden subgraphs)
Tools
Czumaj, Artur and Sohler, Christian (2020) A characterization of graph properties testable for general planar graphs with one-sided error (it's all about forbidden subgraphs). In: The 60th IEEE Symposium on Foundations of Computer Science (FOCS 2019), Baltimore, MD, 9-12 Nov 2019. Published in: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) doi:10.1109/FOCS.2019.00091 ISSN 2575-8454.
|
PDF
WRAP-characterization-graph-properties-testable-general-planar-graphs-one-sided-error-Czumaj-2019.pdf - Accepted Version - Requires a PDF viewer. Download (3498Kb) | Preview |
Official URL: https://doi.org/10.1109/FOCS.2019.00091
Abstract
The problem of characterizing testable graph properties (properties that can be tested with a number of queries independent of the input size) is a fundamental problem in the area of property testing. While there has been some extensive prior research characterizing testable graph properties in the dense graphs model and we have good understanding of the bounded degree graphs model, no similar characterization has been known for general graphs, with no degree bounds. In this paper we take on this major challenge and consider the problem of characterizing all testable graph properties in general planar graphs.
We consider the model in which a general planar graph can be accessed by the random neighbor oracle that allows access to any given vertex and access to a random neighbor of a given vertex. We show that, informally, a graph property P is testable with one-sided error for general planar graphs if and only if testing P can be reduced to testing for a finite family of finite forbidden subgraphs. While our presentation focuses on planar graphs, our approach extends easily to general minor-free graphs.
Our analysis of the necessary condition relies on a recent construction of canonical testers in the random neighbor oracle model that is applied here to the one-sided error model for testing in planar graphs. The sufficient condition in the characterization reduces the problem to the task of testing H-freeness in planar graphs, and is the main and most challenging technical contribution of the paper: we show that for planar graphs (with arbitrary degrees), the property of being H-free is testable with one-sided error for every finite graph H, in the random neighbor oracle model.
Item Type: | Conference Item (Paper) | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TA Engineering (General). Civil engineering (General) |
|||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Computer algorithms, Structural analysis (Engineering) , Graph theory, Graph algorithms | |||||||||||||||
Journal or Publication Title: | 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) | |||||||||||||||
Publisher: | IEEE | |||||||||||||||
ISSN: | 2575-8454 | |||||||||||||||
Official Date: | 6 February 2020 | |||||||||||||||
Dates: |
|
|||||||||||||||
DOI: | 10.1109/FOCS.2019.00091 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Reuse Statement (publisher, data, author rights): | © 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | |||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
Copyright Holders: | IEEE | |||||||||||||||
Date of first compliant deposit: | 30 September 2019 | |||||||||||||||
Date of first compliant Open Access: | 2 October 2019 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Conference Paper Type: | Paper | |||||||||||||||
Title of Event: | The 60th IEEE Symposium on Foundations of Computer Science (FOCS 2019) | |||||||||||||||
Type of Event: | Conference | |||||||||||||||
Location of Event: | Baltimore, MD | |||||||||||||||
Date(s) of Event: | 9-12 Nov 2019 | |||||||||||||||
Related URLs: | ||||||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year