Clutter

A clutter is a set family with no member containing another member. In other context, they are also called Sperner families.

Let $${\mathcal C}$$ be a clutter on ground set V. We investigate the following linear system $$LP({\mathcal C})$$ associated with $${\mathcal C}$$ :

$$\begin{array}{rll} \min wx: \ x(v) & \geq 0 & \text{ for each } v \in V,\\ x(A) & \geq 1 & \text{ for each } A \in {\mathcal C}\\ \end{array}$$

• A clutter $${\mathcal C}$$ packs if both $$LP({\mathcal C})$$ and its dual have integral optimal solutions for $$w={\mathbf 1}$$ .
• A clutter $${\mathcal C}$$ has the packing property if both $$LP({\mathcal C})$$ and its dual have integral optimal solutions if $$w \in \{0,1, +\infty\}^V$$ .
• A clutter $${\mathcal C}$$ has the max flow min cut property (MFMC property for short) if both $$LP({\mathcal C})$$ and its dual have integral optimal solutions if $$w \in \mathbb{Z}_+^V$$ . Equivalently, if $$LP({\mathcal C})$$ is TDI.
• A clutter $${\mathcal C}$$ is ideal if $$LP({\mathcal C})$$ has an integral optimal solution if $$w \in \mathbb{Z}_+^V$$ . Equivalently, if $$LP({\mathcal C})$$ describes an integer polyhedron.

The blocker of a clutter is the clutter of inclusionwise minimal transversals. Given a clutter $${\mathcal C}$$ and an element $$v \in V$$ , the deletion of v means the restriction of the clutter to $$V-v$$ , while the contraction of v is the clutter on ground set $$V-v$$ formed by the inclusionwise minimal elements of $$\{X-v: X \in {\mathcal C}\}$$ . A minor of $${\mathcal C}$$ is a clutter obtained by a sequence of deletions and contractions.

A comprehensive description on the topic can be found in Cornuéjols' book . See also the Wikipedia article.