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 vertex graph : the fractional vertex packing polytope and the vertex packing polytope .

First they prove some properties of . Each extreme point of is shown to be integral or half-integral, that is, for each . They characterize the extreme points of as a sum of particular points in .

They then show an important lifting theorem. Consider any facet-defining inequality for , where is the subgraph induced by the vertex subset . They show that one can lift this inequality so that it is facet-defining for .

The final section of their paper is devoted to *independence systems,* which are based on the notion of heredity*.** *Consider a family of subsets (called independent sets) of a finite set . The pair is called an independence system if (1) and (2) implies . 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 such that . Nemhauser and Trotter characterize those independence systems that have a *graphical *representation. An independence system is proven to be graphical if and only if

- (1) for all , and
- (2) for all for all with .

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.

### Like this:

Like Loading...

*Related*