Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Testing hereditary properties of nonexpanding bounded-degree graphs

Tools
- Tools
+ Tools

Czumaj, Artur, Shapira, Asaf and Sohler, Christian (2009) Testing hereditary properties of nonexpanding bounded-degree graphs. SIAM Journal on Computing, Volume 38 (Number 6). pp. 2499-2510. doi:10.1137/070681831 ISSN 0097-5397.

[img]
Preview
PDF
WRAP_Czumaj,_GetPDFServlet3.pdf - Published Version - Requires a PDF viewer.

Download (375Kb) | Preview
Official URL: http://dx.doi.org/10.1137/070681831

Request Changes to record.

Abstract

We study graph properties that are testable for bounded-degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and graphs that are far from every graph having that property. It is well known that in the bounded-degree graph model (where two graphs are considered "far" if they differ in epsilon n edges for a positive constant epsilon), many graph properties cannot be tested even with a constant or even with a polylogarithmic number of queries. Therefore in this paper we focus our attention on testing graph properties for special classes of graphs. Specifically, we show that every hereditary graph property is testable with a constant number of queries provided that every sufficiently large induced subgraph of the input graph has poor expansion. This result implies that, for example, any hereditary property (e.g., k-colorability, H-freeness, etc.) is testable in the bounded-degree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. No such results have been known before, and prior to our work, very few graph properties have been known to be testable with a constant number of queries for general graph classes in the bounded-degree graph model.

Item Type: Journal Article
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Graph theory
Journal or Publication Title: SIAM Journal on Computing
Publisher: Society for Industrial and Applied Mathematics
ISSN: 0097-5397
Official Date: 2009
Dates:
DateEvent
2009Published
Volume: Volume 38
Number: Number 6
Page Range: pp. 2499-2510
DOI: 10.1137/070681831
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Date of first compliant deposit: 17 December 2015
Date of first compliant Open Access: 17 December 2015
Funder: National Science Foundation (U.S.) (NSF), Deutsche Forschungsgemeinschaft (DFG), Engineering and Physical Sciences Research Council (EPSRC)
Grant number: CCR-0313219 (NSF), EP/D063191/1 (EPSRC), 0354600 (NSF), Me 872/8-3 (DFG)
Version or Related Resource: A preliminary version of this paper, entitled “On testable properties in bounded degree graphs,” authored by the first and third authors, appeared in the Proceedings of the 18th Annual Symposium on Discrete Algorithms (SODA), New Orleans, LA, 2007, pp. 494–501.

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us