Testing Graph Properties Very Efficiently

In this talk, we will survey recent advances on the problem of testing graph properties. We will consider a generic problem that for a given input graph G=(V,E) and a given graph property P (e.g., P may mean bipartiteness, 3-colorability, or planarity), we would like to determine if G satisfies property P or not. While the exact problem as defined here is often known to be computationally very hard (e.g., NP-hard, or even undecidable), we will focus on a simpler task, and we will want to distinguish between the input graphs that satisfy property P from the graphs that are “far away” from satisfying property P. Being “far away” means that one has to modify the input graph in more than, say, 1% of its representation to obtain a graph satisfying property P. We will survey recent results in this area and show that for many basic properties, one can test them in this framework very efficiently, often in sublinear-time, and sometimes even in constant time.