Todays topic is Jonathan Kelner's paper that won the best student paper at STOC a few days ago.
Many people know about the planar separator theorem: every planar graph has a vertex separator (a set of vertices whose deletion separates the graph into two pieces of roughly equal size) of size O(√n). For a bounded degree planar graph the same theorem also shows that there is a cut of sparsity O(1/√n). These results extend to graphs that can be embedded on a surface of genus g - vertex separators of size O(√(gn)) and cuts of sparsity O(√(g/n)) exist. Gilbert, Hutchinson, and Tarjan showed how to find the separator (cut) if the embedding of the graph in a genus g surface is given as part of the input. The catch is that given a graph G, the problem of finding the genus of the graph is NP-hard. It has been an open problem if one could find the separator and cut without finding an explicit embedding.
Another related question is the following. A popular graph partitioning technique used in practice is that of spectral partitioning. Spielman and Teng showed that this algorithm is also good in theory for planar graphs by demonstrating that the algorithm always yields a cut of ratio O(1/√n). They conjectured that the spectral method also works for higher genus graphs and thus pointed a way to overcome the problem of not knowing the genus explicitly.
Kelner's paper resolves the above two problems by proving that the spectral methods yields a cut of sparsity O(√(g/n)). The high level scheme is from Spielman and Teng. Kelner generalizes the scheme using some nice results from algebraic geometry. This result is beautiful because of the connection between combinatorial objects (graphs) and continuous mathematics (ed: Aha !! ).
Here is a brief description of the method. Spielman and Teng use the Koebe-Andreev-Thurston theorem which shows that planar graphs can be obtained as a contact graph of disjoint circles on the plane (or equivalently on the surface of a sphere in 3 dimensions) where there is an edge between two vertices u and v iff the circles corresponding to u and v touch tangentially.
Using this circle packing theorem, Spielman and Teng show via a simple but clever argument that the second eigenvalue of the Laplacian of the graph is O(1/n).
The result for genus g graphs would follow from the same approach if it can be shown that the graph can be obtained by the adjacency graph of circles touching on the sphere with the proviso that any point on the sphere is contained in at most O(g) circles - in other words we allow overlapping circles now. Unfortunately this cannot be done. To overcome this Kelner uses a theorem of He and Schramm that shows that genus g graphs can be obtained by touching circles where the circles are disjoint and embedded on a Riemannian surface of genus g. The technical part of the proof involves mapping the Riemannian surface back onto the sphere via conformal mappings (mappings that preserve angles). Difficulties arise because the original mapping to the Riemannian surface has branch points which are points of singularity and the mapping from the surface to the sphere does not maintain conformality at these branch points. The number of branch points is however limited to O(g) and by using a fine subdivision of the graph it is shown that these singularities do not play a major role.
The above description is at a very high level. The paper of Kelner is short - it uses several important known results from mathematics in a direct and effective way. It is impressive that he knows enough math to know and put them together - most people in the audience at STOC including myself have limited background in the continuous mathematics that is needed to do this proof. I wish that I had more classes in pure math ...(ed: Amen..)
References:
J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan. A separator theorem for graphs of bounded genus. J. Algorithms, 5:391-407, 1984.
No comments:
Post a Comment