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.

Summary:

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.

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