Lecture 30: 04/11/2012

I hope the homework went (is going) well!

Tomorrow (today) we’ll be talking about totally different. We’re gonna dive into some randomized algorithms with the Schwartz-Zippel Lemma.

Try to look it up on the internet before class so you’re not totally lost but here’s some basics:

We have a polynomial a_0 + a_1 x + … + a_d x^d that we’d like to check if it’s the zero-polynomial. That’s easy if we have it in coefficient form (just check if they’re all zero!). But what I give you something like (1 – x)(x + 2x^2 -19x^2)…(1 – x^3)? Well you’d have to multiply it all out (which takes exponential time) and check the coefficients.


Schwartz-Zippel thought: what if you check that polynomial of degree d at some random point? If the value is not 0, then the polynomial can’t be the zero-polynomial. If it was zero, then there’s a good chance the polynomial is zero everywhere. So just repeat this test a bunch of times and if you always get zero, then its probably zero.

It gives us some cool applications so look forward to that!

What a great lecture today!

We first looked at the algebraic or deterministic way of determining if a polynomial is identically 0. You just have to check d+1 points for a polynomial of degree d. That’s great! So why bother with the randomized approach?

If you have a polynomial of degree d in two variables, then you have to check (d+1)(d+1) = d^2 + 2d + 1 points. Now it looks like our linear time algorithm is going to pay off.

We’ll look at how the probability bound changes when we go from one variable to several variables on Friday.

At the end, we looked at a very interesting application of this. We have two sets A and B. We want to check if they’re equal. Well, just sort ’em and check each element one by one. That takes O(n lg n) time, but what if n is huge??

Let A = [a_0, …, a_(n-1)] and B = [b_0, …, b_(n-1)]. Let P_A = (x – a_0)(…)(x – a_(n-1)) and P_B = (x – b_0)(…)(x – b_(n-1)). Now we can check if A = B by asking if (P_A – P_B) == 0. Using our probabilistic algorithm, we can pull this off in linear time and get the correct answer with very very very high probability.


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.

Lecture 26: 03/30/2012

First, a restatement of the HW. I’ll update the post about HW 6 soon so look for that.

Today, we wrapped up the presentation of the polynomial-time planarity algorithm outlined in Wednesday’s lecture. It also gives hints about the linear-time algorithm and where the savings in time is.

The lemma is the main intuition behind why this works. Please study its proof and bring any questions to class (or ask them here)!

We’ll start the Planar Separator Theorem on Monday so please look over that section in Kozen.

HW 6

Phipps Garden Subway Problem

Written submission is due in lecture on Wednesday, April 11 2012.

I’m updating this post according to the restatement given in lecture on Friday.

You’re given a map of a subway rail system (planar graph). Each face (except the outer one) of the planar graph is a country with a train that travels around it continuously in the clockwise direction.

All vertices are intersections of track of degree 3. Furthermore, the graph is 2-edge-connected, meaning you can’t delete a single edge and disconnect the graph.

Prove that there is a scheduling algorithm that guarantees no gridlocks and no starvation.

No gridlocks means that trains may only travel in one direction on a rail at one time. No starvation means that every train must make infinitely many trips around its face.

If the planar graph is embedded on a sphere, there’s now an outside country that has a train traveling clockwise. Prove that there is no scheduling algorithm.

Lecture 25: 03/28/2012

More Planarity.

We have a new HW assignment due next Wednesday. I’ll make a separate post for it.

How do we represent a planar graph? Well, I could tell you that a graph is planar, but that does you no good. I need to give you an embedding (without crossing edges), but how do I write it down?

We may represent an (unordered) edge as a pair of directed edges, one in each direction: e and e_

The _ operation reverses the direction of the edge, i.e., (e)_ = e_ and (e_)_ = e.

\theta is an orientation function of the edges around each vertex.

As we saw in the example in class, we can assign an orientation to every edge of a planar graph. It would be nice if we could show that this is possible only if the graph is planar. However, this isn’t true.

K_5 and K_(3,3) can be embedded, on some surfaces, just not the plane or a sphere. It is possible to embed them on a torus.

THM: Any graph can be embedded on some surface, i.e., sphere, torus, two-handled torus, etc.
COR: Any graph is locally planar.

How does a polynomial-time algorithm for embedding a graph work?
We’re given a graph G = (V, E). Start by finding a cycle in G. Find a path that cuts the cycle in half. At this point, we have three faces (two inner faces and the outside face).

Keep finding paths from the inside of a path to the inside of another path. Each time we insert a new path, we cut an existing face in two.

If we reach a point where the only paths left to insert are from a path to itself, we simply run the above procedure locally.

If at some point you can’t add a path without cutting across an edge, then the graph isn’t planar.

Study this algorithm and come up with some good questions for Friday’s lecture.