Clutter

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

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

[math] \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} [/math]

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

The blocker of a clutter is the clutter of inclusionwise minimal transversals. Given a clutter [math]{\mathcal C}[/math] and an element [math]v \in V[/math], the deletion of v means the restriction of the clutter to [math]V-v[/math], while the contraction of v is the clutter on ground set [math]V-v[/math] formed by the inclusionwise minimal elements of [math]\{X-v: X \in {\mathcal C}\}[/math]. A minor of [math]{\mathcal C}[/math] 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.