Property Testing in Graphs of General Density
Speaker: Michael Krivelevich , Tel Aviv University
Date: March 7 2006
Time: 4:15PM to 5:15PM
Location: 4-237 (refreshments in RSA G5 Lounge)
Host: Ronitt Rubinfeld, Massachusetts Institute of Technology
Contact: Kevin Matulef, 3-5883, matulef@mit.edu
Relevant URL: http://theory.csail.mit.edu/toc-seminars/Graph Property Testing deals with distinguishing between graphs satisfying a certain graph property P, and those who are sizably far from having P, in a sense that a constant fraction \epsilon of their description needs to be modified to get a graph from P. Usually, randomness is allowed (and in fact plays a crucial role in most of the algorithms) and algorithms with query complexity, sublinear in the input size, or even depending on the distance parameter \epsilon only, are sought after.
Traditionally, two models of testing graph properties have been considered. In the first one, introduced by Goldreich, Goldwasser and Ron in 1996, an input graph G is represented by its adjacency matrix, and an algorithm queries whether a pair of vertices u,v forms an edge of G. The second one, due to Goldreich and Ron (1999), assumes that G is represented by the incidence lists of its vertices, and the algorithm queries for the i-th neighbor of vertex v. The former model is appropriate for dense graphs, i.e. graphs with a quadratic number of edges, while the latter is tailored for testing bounded degree graphs.
Recently, a hybrid model, combining the previous two models, has emerged. In this model, an input graph is thought of to be represented by both adjacency matrix and incidence lists, and an algorithm is allowed to ask both types of queries, i.e., vertex-pair queries of the dense model and neighbor queries of the bounded degree model. This approach allows to circumvent the inherent drawbacks of the more traditional models and is thus suitable in principle for testing graphs of arbitrary density.
I will discuss this model and recent results pertaining to it, such as testing bipartiteness and H-freeness, for a fixed graph H.
See other events that are part of Theory Colloquium Spring 2006
See other events happening in March 2006
