Covering number

Let S be a finite set, and F a collection of subsets of S. The covering number of (S,F) is the minimum number of members of F whose union is S. Related definitions:

• The fractional covering number of (S,F) is [math]\min\{\sum_{Z \in F} x_Z:\ x \geq 0,\ \sum_{Z\in F: s \in Z} x_Z \geq 1\ \forall s \in S \}.[/math]
• The circular covering number of (S,F) is the minimum circumference of a circle C for which it is possible to place the elements of S along the circle so that the elements placed in a unit interval [math][x,x+1)[/math] are contained in a single member of F.
• Given [math]w: S \to {\mathbb Z}_+[/math], the [math]w[/math]-covering number of (S,F) is [math]\min\{\sum_{Z \in F} x_Z:\ x \in {\mathbb Z}_+^F,\ \sum_{Z\in F: s \in Z} x_Z \geq w(s) \ \forall s \in S\}.[/math]

Vertex cover

The vertex cover number of (S,F) is the minimum number of elements of S so that at least one element is chosen from every member of F. In other words, the vertex cover number is the covering number of the hypergraph defined by the transposed matrix. The fractional and circular vertex cover numbers can be defined similarly as the fractional and circular covering numbers of the transposed hypergraph.

In particular, a vertex cover of a graph G is a set of vertices that contains at leas one endpoint of every edge. Given [math]w: E \to {\mathbb Z}_+[/math], a [math]w[/math]-vertex cover of G is a vector [math]x\in {\mathbb Z}_+^V[/math] such that [math]x_u+x_v \geq w(uv)[/math] for every [math]uv \in E[/math].