Chvátal | Farkas' Dilemma

A good characterization has both a short proof and a short refutation (i.e., belongs to $NP \cap coNP$ ). Jack Edmonds is a big believer in good characterizations, and he and fellow proselytizer Václav Chvátal did a lot of preaching. For the record, I support the hype. Good characterizations give an unreasonable amount of insight into a problem.

Good characterizations often foreshadow polynomial-time solvability. Linear programming (LP) is a famous example. Long before the ellipsoid method was shown to solve LPs in polynomial time, it was known that the question — is the optimal objective of this (maximization) LP at least $z$ ? — has both a short proof and short refutation*. Given a possible solution, one can quickly check that it satisfies the constraints and that its objective is indeed at least $z$ . For the short refutation, we have duality; simply provide a feasible solution to the dual problem that has objective less than $z$ .

The maximum clique and the vertex coloring problems have a similar sort of weak ‘duality’. That is, the clique number $\omega (G)$ and chromatic number $\chi (G)$ of a graph $G$ satisfy $\omega (G) \le \chi (G)$ . For LPs there is strong duality; the objectives of the primal and dual LPs are equal whenever both are feasible. For clique and coloring, the ‘duality’ can be very weak. Indeed, there is a class of graphs for which the clique number is two, but the chromatic number can be arbitrarily large. Thus, we may not be able to refute the question — is the clique number at least $k$ ? — with a proper coloring. It seems that there will never be such a good characterization for either clique or coloring (unless coNP=NP).

But what happens if we restrict ourselves to the class of graphs for which $\omega (G) = \chi (G)$ ? In this case, we DO have a sort of strong duality. We can now quickly verify that $\omega (G) \ge k$ when given a clique of size $k$ , and we can refute $\chi (G) \ge k$ if given a $(k-1)$ -coloring. So, we have our good characterization, and you know what? For this restricted class of graphs, we CAN solve maximum clique in polynomial time! If we further restrict ourselves to the class of perfect graphs, where $\omega (G')=\chi(G')$ for every vertex-induced subgraph $G'$ of $G$ , then all sorts of mathematical beauty emerge.

This leads me to the research topic generator: First look for a good characterization. If you can’t find one, artificially impose it and see what happens.

________________________________________________

*The proof that LP belongs to NP or coNP is actually more complicated than I make it seem. One needs to show that there is an optimal solution whose size (when represented in binary) is polynomial in the input size.

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.

Farkas' Dilemma

Tag Archives: Chvátal

Good characterizations and perfect graphs

Great papers: Edmonds Polytopes and a Hierarchy of Combinatorial Problems