Great papers: Properties of Vertex Packing and Independence System Polyhdera

I’ve decided to read and summarize one great paper a week from this list. For the first paper, I’ve chosen Nemhauser and Trotter‘s 1974 paper Properties of Vertex Packing and Independence Systems Polyhedra.


Nemhauser and Trotter consider vertex packing polyhedra and independence system polyhedra (which are more general). A vertex packing is a subset of vertices that induces an edgeless graph. It is also known as a stable set, an independent set, or an anticlique (the last one is new to me).  They consider two polyhedra for an n-vertex graph G=(V,E): the fractional vertex packing polytope \mathcal{L}_G and the vertex packing polytope \mathcal{B}_G.

\mathcal{L}_G = \{ x \in \mathbb{R}^n_+ | x_i + x_j \le 1~\forall (i,j) \in E \}
\mathcal{B}_G = conv( \mathbb{Z}^n \cap \mathcal{L}_G )

First they prove some properties of \mathcal{L}_G. Each extreme point x' of \mathcal{L}_G is shown to be integral or half-integral, that is, x'_j=0,\frac{1}{2},\text{ or }1 for each 1\le j \le n. They characterize the extreme points of \mathcal{L}_G as a sum of particular points in \mathcal{L}_G.

They then show an important lifting theorem. Consider any facet-defining inequality for \mathcal{B}_{G[S]}, where G[S] is the subgraph induced by the vertex subset S \subset V. They show that one can lift this inequality so that it is facet-defining for \mathcal{B}_G.

The final section of their paper is devoted to independence systems, which are based on the notion of heredity. Consider a family \mathcal{I} of subsets (called independent sets) of a finite set I. The pair (I,\mathcal{I}) is called an independence system if (1)\emptyset \in \mathcal{I} and (2)I_1 \subset I_2 \in \mathcal{I} implies I_1 \in \mathcal{I}. Thus in an independence system, every subset of an independent set is independent, and there exists at least one independent set. (Note: add the augmentation property to an independence system and you have a matroid.)

It is clear that the vertex packings of a graph can be naturally represented as an independence system, but the converse is not true. For example, any single vertex in a graph is a vertex packing, but there may be a single element i \in I such that \{ i\} \notin \mathcal{I}. Nemhauser and Trotter characterize those independence systems that have a graphical representation. An independence system (I, \mathcal{I}) is proven to be graphical if and only if

  • (1) \{i\} \in \mathcal{I} for all i \in I, and
  • (2) I_0 \setminus \{i\} \in \mathcal{I} for all i \in I_0 \implies I_0 \in \mathcal{I} for all I_0 \subseteq I with |I_0|>2.

They then consider the generalization of the weighted vertex packing problem for independence systems. They show that the lifting theorem for vertex packing generalizes for independence systems.


Next up: V. Chvátal, Edmonds Polytopes and a Hierarchy of Combinatorial Problems, Discrete Mathematics 4 (1973), 305.

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