Minimum size transversals in uniform hypergraphs

A set of vertices in a hypergraph which meets all the edges is called a transversal. The transversal number τ ( H ) of a hypergraph H is the minimum cardinality of a transversal in H . A classical greedy algorithm for constructing a transversal of small size selects in each step a vertex which has the largest degree in the hypergraph formed by the edges not met yet. The analysis of this algorithm (by Chvátal and McDiarmid (1992)  [3]) gave some upper bounds for τ ( H ) in a uniform hypergraph H with a given number of vertices and edges. We discuss a variation of this greedy algorithm. Analyzing this new algorithm, we obtain upper bounds for τ ( H ) which improve the bounds by Chvátal and McDiarmid.