Great papers: The Complexity of Facets (and Some Facets of Complexity)

I’ve decided to read and summarize one great paper a week (or month, or semester…) from this list. This week’s paper is the 1984 paper The Complexity of Facets (and Some Facets of Complexity) by Christos H. Papadimitriou and Mihalis Yannakakis. Also see an earlier and shorter version of the paper in the proceedings from STOC ’82.

Summary:

Papadimitriou and Yannakakis consider a particular class of problems called DP. Problems in this class have two parts: one part belongs to NP and the other belongs to coNP. The authors show that a number of interesting problems are complete for the class DP.

An example of a DP problem is: given a graph is the size of its maximum clique exactly k? The NP part is — is the maximum clique size at least k? (This belongs to NP because, given a clique of size k, one can easily confirm that it is a solution.) The coNP part is — is the maximum clique size at most k? (This belongs to coNP since the claim “the maximum clique size is at most k” can be refuted by providing a larger clique.) This EXACT CLIQUE problem turns out to be complete for the class DP.

Several notable types of DP problems are mentioned:

  1. Facets. For example, given an inequality and a graph, does the inequality induce a facet of the graph’s clique polytope? The NP part is to provide the proper number of affinely independent integer feasible points that satisfy the inequality at equality, and the coNP part is to verify that the inequality is actually valid.
  2. Critical problems. For example, is a graph maximal nonHamiltonian (meaning it has no Hamiltonian cycle, but the addition of any edge makes it Hamiltonian)?
  3. Exact problems. For example, is the maximum clique size exactly k?
  4. Unique solution problems. For example, does a given boolean formula have exactly one satisfying assignment?

The majority of the paper is spent providing reductions to show that many problems are DP-complete. Of all the problems mentioned, these may be of the most interest to the OR community:

  1. TSP FACETS. Does a given inequality induce a facet of the TSP polytope?
  2. CLIQUE FACETS. Does a given inequality induce a facet of clique polytope of a given graph?
  3. EXACT TSP. Is the optimal TSP tour of length exactly k?
  4. TSP Supporting Hyperplane. Is a given inequality valid and does it have nonempty intersection with the TSP polytope?
  5. Critical Integer Programming. Given a system of linear inequalities, is it true that it has no integer solution, but the removal of just one constraint makes the system integer feasible?

Another problem — Interior Points — is shown to be NP-complete. This problem asks: given a point and a polyhedron, does the point belong to the polyhedron’s integer hull?

Next up: J. Edmonds, Paths, Trees, and Flowers, Canadian Journal of Mathematics 17 (1965), 449.

Advertisements

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