Good characterizations and perfect graphs

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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your 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