Lecture 17: Separation for Odd Cuts

Yesterday we reduced the separation problem for the matching polytope to the following problem:

given an undirected graph G, find a minimum cut (A,A')
such that A has odd cardinality,
and A does not contain the special vertex s.

We showed that if the weight of the edges crossing such a min-cut was strictly less than 1, then A would correspond to a violated constraint in the (exponentially-sized) LP. And one could find the min-cut (B, B') in the graph in polynomial time. But what if the side B not containing the special vertex s in this min-cut turned out to be of even cardinality? Well, It turns out we need a little more work.

To handle this, we do the following: first, we recurse on G/B (which is the graph obtained by shrinking the set B to a single node), and on G/B' obtained by shrinking B' to a single node. In the latter, we treat the new node obtained from shrinking B' as the "special" node.

Why would one of the two recursions succeed in finding a minimum odd cut? Suppose (A, A') was a minimum odd cut we were looking for (with s not in A). Recall that (B, B') was the mincut but B was even. And s is in neither of A or B,

• If A lay completely inside B or B', we'd find it in one of the recursive calls.
• If A contains B, we'd find it the recursive call on G/B.
  
• Suppose A intersects both B and B' but does not contain B. Then consider the 4 parts: A cap B, A cap B', A' cap B, and A' cap B'. |A| is odd, |B| is even. So either |A cap B| is odd, or |A cap B'| is odd.
  
  
  1. Say it's the former: |A cap B| is odd. A' cap B' contains s, so it's non-empty.
     
     Now we bust out the following fact (which is called submodularity of the cut function): if cut(X) is the weight of all edges going out of some set X,
     
     cut(X) + cut(Y) >= cut(X cap Y) + cut(X cup Y).
     
     
     So cut(A) + cut(B) >= cut(A cap B) + cut(A cup B) = cut(A cap B) + cut(A' cap B').
     
     cut(A) = min-odd-cut.
     cut(B) = min-cut.
     cut(A' cap B') >= min-cut, since A' cap B' is non-empty.
     cut(A cap B) >= min-odd-cut.
     
     Putting these together, the only way to satisfy submodularity is when we have equality everywhere. so cut(A cap B) = min-odd-cut, and we will find it recursively.
     
     
  2. If it's the latter: |A cap B'| is odd. Since A does not contain all of B, A' cap B is non-empty. Now apply submodularity to A and B', and repeat the same argument.
  
  This shows that at least one of the recursive calls to G/B or G/B' still has an odd-cut with the same value as cut(A), and hence we will find it recursively.
  

Finally, we need to bound the runtime of the entire procedure, but that can be bounded by poly(n).

Long-delayed Posts I: the Hirsch Conjecture

In Lecture 16, when we'd mentioned the simplex algorithm, I'd mumbled something about the diameter of polytopes and the Hirsch conjecture --- here are some details.

If you consider a polyhedron defined in d dimensions by the intersection of n half-spaces, then the Hirsch conjecture says that the diameter of the 1-skeleton of such a polyhedron is at most n-d. We've been using n dimensions (variables) and m half-spaces (constraints), but I will stick with the n,d notation --- you can do the translation. Kalai and Kleitman showed (in this two-page paper) that the diameter is at most n^{2 + log d} --- and this is essentially the best result known.

This problem was of interest to us, because if the diameter of some LP polytope were indeed large, then the simplex algorithm starting from a bad vertex might require a large number of steps. Of course, we only care about polynomiality, so we would be happy with the polynomial Hirsch conjecture: the diameter of the 1-skeleton is at most poly(n,d).

Some more resources:

• A series of blog posts by Gil Kalai's blog: here is one of them. His posts contain a huge wealth of information about the conjecture, its variants and generalizations.
  
• A recent survey by Santos and Kim.

Lecture 15 notes

Some notes about today's lecture:

1. I mentioned that there are integrality results for some natural LPs for MST, branchings, shortest paths, matchings. Basically, this means that one can write LPs for these problems such that the basic solutions (i.e., vertices of the resulting polytope) are all 0-1 vectors. It was all a bit too fast towards the end, and so we will try to cover integrality for LPs in another lecture later.
   
   
2. For the branchings LP to make sense for negative edge weights, we should throw in a constraint that the total number of arcs chosen is at most n-1 (or that at most one arc should be chosen from the out-arcs of each non-root vertex). Else negative edge weights might cause the LP to choose too many edges, or even to choose edges to an extent greater than 1.
   
   
3. Finally, Srivatsan wondered about the fact that the size of the LP we wrote for branchings was exponentially sized: what's up with that? Two answers to this.
   
   One: we can use the LP purely for analytical purposes. If we use Edmonds' cycle shrinking algorithm from Lecture 5, we end up showing an integer primal solution of some value, and a feasible dual solution of the same value. And since these primal and dual solutions are feasible, and of equal value, both must be optimal!
   
   Second: wait until next lecture, we will show how to solve this exponentially sized LPs under certain conditions. For now, just observe that that if you are given a feasible (fractional) solution x, and it does not satisfy all the constraints, you can find some violating contraint in polynomial time. (In case there is a set S such that strictly less than 1 unit of x_e crosses it, there is a min-cut separating some vertex from the root with value strictly less than 1.) Note that if x is not in the branching polytope, this efficient procedure gives us a hyperplane that separates x from the polytope, and hence is called a "separation oracle" for this polytope.
   
   
4. Finally, I mentioned that Edmonds' result shows that every vertex of the polytope defined by the branching LP was integral. This is a slightly subtle point, so I'd like to elaborate.
   
   Edmonds shows that given edge-costs, the branching found by his algorithm wrt these edge costs is also an optimal LP solution for those edge-costs (since he gives a branching that is feasible for the primal, and a matching set of weights that are feasible for the dual).
   
   Now suppose the branching polytope has a fractional vertex (i.e., a extreme point z of this polytope such that not every coordinate of z is 0 or 1). One can show (using convexity etc) there exists some cost vector c for which this extreme point z is the unique optimal solution to the branching LP. But that would contradict the fact that for those edge costs, Edmonds' algorithm would find an integral optimal solution.

Next Monday, we'll give a quick overview of simplex, and then some details about the ellipsoid algorithm.

Notes on Lecture 14

A proof of the inequality we used (courtesy Danny):

To prove: Log[1 + b] >= 2 b/(2 + b) for b>=0
Note that it's equal when b=0.
You take the derivative of
Log[1 + b] - 2 b/(2 + b), and get
b²/((1 + b) (2 + b)²). This is non-negative
for b>=0. QED.

Wednesday's Lecture

For Wednesday's lecture (it will be on basics of LPs and duality), have a quick look over the proof of optimality of branchings we did way back in Lecture 5. We'll then give some algorithms to solve LPs in the next couple of lectures.

Monday's Lecture

Sorry to change things around, but I'll cover some probabilistic inequalities (a.k.a. large-deviation bounds, concentration bounds, Chernoff-type bounds, whatever you might want to call them) in Monday's lecture. Wednesday we'll finally get started on LPs...

Clarification of Today's Lecture

I've posted the complete and correct argument that I should have used in today's lecture. It's here. I suggest you read it right now while the lecture is still fresh in your mind.