Testing minor-closed properties in sparse graphs

Terry Tao and Gil Kalai have written on the mathematical work of Oded Schramm. Tao suggests a survey paper by Lawler as a source to learn more about the stochastic Loewner equation and its applications. Schramm was a plenary speaker at the 2006 ICM in Madrid, and his talk can be seen going to http://www.icm2006.org/video/ and clicking on “11th Session.” Unfortunately the site is very badly designed and, on my computer, it works neither with Firefox nor with Chrome. (It does work with IE.)

Oded has also worked in computer science, and here I would like to recall a lovely recent paper of his on property testing.

In graph property testing, we are interested in a graph property such as, say, 2-colorability, and we would like to develop very efficient algorithms, at the cost of delivering an approximate answer. The approximation takes the following form: if the graph is 2-colorable, then we want the algorithm to accept with high probability, and if the algorithm accepts with noticeable probablity, then it must be the case that the graph is at least “\epsilon-close” to 2-colorable. (A similar definition can be given for any other graph property, such as connectivity, planarity, expansion, 3-colorability, and so on.)

The notion of “closeness” can be defined in various ways, which affect the complexity of the problem.

If we deal with dense graphs, we usually define two n-vertex graphs to be “\epsilon-close” if one can be converted into the other by adding or removing at most \epsilon n^2 edges. In this “dense graph model” of property testing, the notion of closeness is loose enough that essentially every natural graph property has very efficient algorithms, whose running time depends only on \epsilon.

If we deal with sparse graphs, such as graphs whose maximum degree is d (think of d as a constant, while the number n of vertices goes to infinity), then we would say that two graphs are \epsilon-close if one can be converted into the other by adding or removing up to \epsilon d n edges. In this “bounded degree graph model” of property testing, some properties become much harder to test. While 2-colorability, and, in fact, k-colorability for every k, have testers of complexity poly(1/\epsilon) in the dense graph model, 2-colorability as complexity \Omega (\sqrt n) and O(\sqrt n polylog n) and 3-colorability has complexity \Omega(n) in the bounded degree model.

Also, some properties are trivial in the dense graph model and non-trivial in the bounded-degree one. Consider planarity: in the dense graph model, a graph is \epsilon-close to planar if and only if it is (\epsilon + o(1))-close to the empty graph, and so testing planarity is equivalent to testing emptiness, and thus trivial. In the bounded-degree model, it had been an open question to find a sub-linear time tester for planarity.

In STOC 2008, Benjamini, Schramm and Shapira prove that planarity is testable in the bounded-degree model with complexity that depends only on \epsilon, and independent of the size of the graph. The same result applies to any graph property defined in terms of excluded minors. Previously, very few properties were known to be testable with complexity dependent only on \epsilon in this model.

The proof applies more broadly to properties that are “hyper-finite,” meaning that graphs with the property can be broken up into finite-size components after removing a small fraction of edges. The result relies on a previous result by Schramm, studying “limits” of sequences of hyper-finite graphs using the kind of compactness techniques described by Terry Tao in his recent MSRI lectures.

4 thoughts on “Testing minor-closed properties in sparse graphs

  1. Pingback: Oded « Combinatorics and more

  2. Pingback: Oded Schramm « What’s new

  3. Pingback: Oded Schramm « Almost Surely

  4. I have tested 5 different paper products for suitability of recycling into actual sheets of paper, for a school project. I tested egg cartons, paper towels, wrapping paper, magazines, newspapers. I now know the properties of each recycled product eg firm, soft and pliable, easily folded, can be written on, etc. How could I graph those results please?
    Thank you if you can help me.
    Felicity Cook

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s