Artur Czumaj
Testing graph properties very efficiently
Abstract: 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.