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