# 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