transversaalset

Transversaalset, commonly referred to as a hitting set in combinatorics, is defined relative to a collection F of sets. A transversal T is a set of elements that intersects every member of F; that is, for every S in F, T ∩ S ≠ ∅. If F is viewed as a hypergraph with vertex set V and edge set E, T is a subset of V meeting every edge in E. The smallest possible size of such a T is called the transversal number, denoted tau(F). A transversal is minimal if no proper subset is a transversal.

In graphs, where F consists of the edge-vertex incident pairs (each edge is a 2-element set), a transversal is precisely a vertex cover: a set of vertices that touches every edge.

Computationally, finding a minimum transversal is NP-hard. The decision version asks whether a transversal of size at most k exists. This is equivalent to the minimum hitting set problem and, in graphs, to the minimum vertex cover problem. Approximations exist; the greedy algorithm yields an O(log n)-approximation for general set systems, and hardness results imply logarithmic inapproximability unless P=NP.

Variants and related notions include transversals of a partition (one element chosen from each block, also known as systems of distinct representatives in some contexts) and transversals of set systems in SDR theory. Transversals have applications in database query optimization, fault diagnosis, network design, and bioinformatics.