Lecture 29: 04/06/2012

A slight modification to statement of the theorem today.

All we care about is that we get one set A such that: n/3 <= |A| <= 2n/3. The original statement follows from this one but it allows us to focus on getting a small partition into A, S, and the rest of the graph.

We had a little review of the previous lecture material but today's focus is on partitioning the set between t_0 and t_2 (defined last time).

First, we add an artificial vertex "s" and put in edges to every vertex of L(t_0) and keep the BFS tree from before up until L(t_2). The depth of this new tree, T, is at most sqrt(n) because t_0 and t_2 were chosen so that t_2 – t_0 <= sqrt(n).

We'll triangulate T and start with an two paths starting at s to a leaf in L(t_2). The vertices along these two paths will be part of the separator set S. For each vertex in T, we can calculate the number of vertices interior and exterior to the separator set using some sort of dynamic programming. We shrink the interior until we have at between n/3 and 2n/3 vertices in it.

We'll probably get another lecture on the separator theorem and cover some applications of it. Please review the boards and the book for Monday's lecture.

Lecture 28: 04/04/2012

Planar Separator Theorem.

Last time, we covered the main definitions associated with the statement of the theorem and today we dove into the proof/algorithm.

The algorithm is somewhat involved and consists of quite a few steps.

First, we need to embed the graph G in the plane (using our linear-time Hopcroft-Tarjan algorithm), otherwise it wouldn’t make sense to try and separate this graph in the plane.

We run a BFS traversal starting at an arbitrary vertex v and assign to each vertex its BFS level. We denote the vertices at the kth level by L(k). Since edges in a BFS traversal only go between vertices in the same level or adjacent levels, any such set L(k) is actually a separator.

We’ll look at level t_1, which is the “middle” level, i.e., the one containing the (n/2)th vertex in the traversal. If the size of L(t_1) is at most 4 sqrt(n), then we’re done, since it separates the graph into two components, A and B, where each is the set of vertices in levels before and after t_1, respectively. We also know that each of these has at most n/2 vertices.

Alas, this isn’t always the case in algorithms. So what if L(t_1) is too big? We’ll find levels t_0 t_1 as close as possible to t_1 so that the size of L(t_0) and L(t_2) is no bigger than sqrt(n).

What do these give us? We now have three partitions of the BFS tree into C, D, and E of vertices before t_0, between t_0 and t_2, and after t_2, respectively.

If the size of D is at most 2n/3, then we’re done. Why?

Say D has at least n/3 vertices, then the other two sets have at most 2n/3 vertices among them, so we take A = D and B to be the union of C and E. The separator in this case is just the disjoint union of L(t_0) and L(t_2).

If D has less than n/3 vertices, then one of the other two sets must have at least n/3 – O(sqrt(n)) vertices, otherwise we violate the law of conservation of mass and lose some vertices. WLOG, say this set is C, then we let A = C and B is the union of D and E.

Are we done yet?? We still need to consider the case that D is bigger than 2n/3. At least it shrunk by a little bit, so as we noted in lecture, we could just recurse and build A, B, and S that way.

Another way to deal with D is to split it “in half” once and be done with it.

We’ll finish up the proof on Friday. Study the cases well and bring any questions to class or ask them here.

Lecture 27: 04/02/2012

Today’s topic: The Planar Separator Theorem.

What does it say? A planar graph on n vertices has a small “separator,” meaning we can partition the set of vertices into three sets A, B, and S such that:
1) |A|, |B| <= 2n/3
2) |S| <= 4 sqrt{n}
3) There is no edge between A and B.

We started the proof of the theorem today and solved the first few cases. If the graph is already disconnected, and the components are small enough, there isn't much to do.

If one of the components is too big, or if the graph itself is connected, we actually have to find a separator set. The process of finding such a separator starts with a BFS traversal and labeling of the levels.

Please review the boards and the book before Wednesday's class. We'll finish up the theorem next time so bring all of your questions (or ask them here)!

We also have a small correction to the homework assignment which I will correct in its own post.