Great papers: Edmonds Polytopes and a Hierarchy of Combinatorial Problems

I’ve decided to read and summarize one great paper a week from this list. This week’s paper is Václav Chvátal‘s 1973 paper Edmonds Polytopes and a Hierarchy of Combinatorial Problems. (The 2006 reprint is easier on the eyes.)

First let me say that this is the only paper that I have seen that cites The Electric Kool-Aid Acid Test. But if you’ve seen the picture of Chvátal in Bill Cook’s In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation this might not come as a surprise. (I can’t seem to find the picture online, sorry. Read the book; it’s great!)

Summary:

In this paper, Chvátal introduces fundamental concepts in Integer Programming and cutting-plane theory. These contributions include the Chvátal-Gomory (CG) procedure for generating valid inequalities, the CG Rank of an inequality, and the CG closure of a polyhedron.

Consider a set S of linear inequalities that define a bounded polyhedron P. Chvátal defines the closure of S to be the smallest set of inequalities that contains S and is closed under two operations: (1) taking linear combinations of inequalities, (2) replacing an inequality \sum_{j=1}^n a_j x_j \le a_0 (for integer a_j) with \sum_{j=1}^n a_j x_j \le a with a \ge \lfloor a_0 \rfloor.

The first operation aggregates inequalities, and every point in P will satisfy the aggregated inequality. However, the second operation is key and can remove fractional points (but not integral points) from P. In other words, inequalities derived from operation (1) are valid for P, and inequalities from operation (2) are valid for P\cap \mathbb{Z}^n.

The rank of an inequality (with respect to the set S of inequalities) is the minimum number of iterations of operation (2) needed to generate the inequality. Chvátal proves that there is no upper bound on the rank of inequalities for the independent set polytope (when using the edge formulation). It is important to note, however, that for any fixed graph the inequalities of the independent set polytope have finite rank.

At the beginning of the paper, Chvátal discusses Jack Edmonds’ notion of good characterizations. In particular, he considers Tutte’s theorem characterizing those graphs that have a perfect matching. This theorem is considered a good characterization in that it shows that the question “does the graph have a perfect matching?” has both a short proof and a short refutation. In other terms the perfect matching problem belongs to both \textbf{NP} and \textbf{co-NP}. (This is trivial now since the perfect matching problem belongs to the class \textbf{P} and \textbf{P} \subset \textbf{NP} \cap \textbf{co-NP}.)

In sections 5 and 6, Chvátal shows that the CG procedure can be used to answer various combinatorial problems. For example, it can be used to show that the Petersen graph has no Hamiltonian circuit. In another example, he shows that the answer to Moser’s cube problem (in three dimensions) is 16.

Next up: J. Edmonds, Matroids and the Greedy Algorithm, Mathematical Programming 1 (1971), 127.

Advertisements

One thought on “Great papers: Edmonds Polytopes and a Hierarchy of Combinatorial Problems

  1. Pingback: Good characterizations and perfect graphs « Farkas' Dilemma

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s