Efficient testing of bipartite graphs for forbidden induced subgraphs

Noga Alon; Eldar Fischer; Ilan Newman

doi:10.1137/050627915

Efficient testing of bipartite graphs for forbidden induced subgraphs

Noga Alon, Eldar Fischer, Ilan Newman

Research output: Contribution to journal › Article › peer-review

36 Scopus citations

Abstract

Alon et. al. [N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 (2000), pp. 451-476] showed that every property that is characterized by a finite collection of forbidden induced subgraphs is ε-testable. However, the complexity of the test is double-tower with respect to 1/ε, as the only tool known to construct such tests uses a variant of Szemerédi's regularity lemma. Here we show that any property of bipartite graphs that is characterized by a finite collection of forbidden induced subgraphs is ε-testable, with a number of queries that is polynomial in 1/ε. Our main tool is a new "conditional" version of the regularity lemma for binary matrices, which may be interesting on its own.

Original language	English (US)
Pages (from-to)	959-976
Number of pages	18
Journal	SIAM Journal on Computing
Volume	37
Issue number	3
DOIs	https://doi.org/10.1137/050627915
State	Published - 2007
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Keywords

Approximation
Graph algorithms
Property testing
Regularity lemma

Access to Document

10.1137/050627915

Cite this

@article{ceb68e031aeb4c2f860a246bbefe8675,

title = "Efficient testing of bipartite graphs for forbidden induced subgraphs",

abstract = "Alon et. al. [N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 (2000), pp. 451-476] showed that every property that is characterized by a finite collection of forbidden induced subgraphs is ε-testable. However, the complexity of the test is double-tower with respect to 1/ε, as the only tool known to construct such tests uses a variant of Szemer{\'e}di's regularity lemma. Here we show that any property of bipartite graphs that is characterized by a finite collection of forbidden induced subgraphs is ε-testable, with a number of queries that is polynomial in 1/ε. Our main tool is a new {"}conditional{"} version of the regularity lemma for binary matrices, which may be interesting on its own.",

keywords = "Approximation, Graph algorithms, Property testing, Regularity lemma",

author = "Noga Alon and Eldar Fischer and Ilan Newman",

year = "2007",

doi = "10.1137/050627915",

language = "English (US)",

volume = "37",

pages = "959--976",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Efficient testing of bipartite graphs for forbidden induced subgraphs

AU - Alon, Noga

AU - Fischer, Eldar

AU - Newman, Ilan

PY - 2007

Y1 - 2007

N2 - Alon et. al. [N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 (2000), pp. 451-476] showed that every property that is characterized by a finite collection of forbidden induced subgraphs is ε-testable. However, the complexity of the test is double-tower with respect to 1/ε, as the only tool known to construct such tests uses a variant of Szemerédi's regularity lemma. Here we show that any property of bipartite graphs that is characterized by a finite collection of forbidden induced subgraphs is ε-testable, with a number of queries that is polynomial in 1/ε. Our main tool is a new "conditional" version of the regularity lemma for binary matrices, which may be interesting on its own.

AB - Alon et. al. [N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 (2000), pp. 451-476] showed that every property that is characterized by a finite collection of forbidden induced subgraphs is ε-testable. However, the complexity of the test is double-tower with respect to 1/ε, as the only tool known to construct such tests uses a variant of Szemerédi's regularity lemma. Here we show that any property of bipartite graphs that is characterized by a finite collection of forbidden induced subgraphs is ε-testable, with a number of queries that is polynomial in 1/ε. Our main tool is a new "conditional" version of the regularity lemma for binary matrices, which may be interesting on its own.

KW - Approximation

KW - Graph algorithms

KW - Property testing

KW - Regularity lemma

UR - http://www.scopus.com/inward/record.url?scp=46449134870&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=46449134870&partnerID=8YFLogxK

U2 - 10.1137/050627915

DO - 10.1137/050627915

M3 - Article

AN - SCOPUS:46449134870

SN - 0097-5397

VL - 37

SP - 959

EP - 976

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

Efficient testing of bipartite graphs for forbidden induced subgraphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this