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 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.