Hitting set

From Wikipedia, the free encyclopedia

You have new messages (last change).

The hitting set problem is an NP-complete problem in set theory. Informally, we are given a collection of subsets S of a universe T and asked to find a subset H of T that intersects ("hits") every set in S. In other words, every set in S must contain at least one element of H. We additionally require that H have at most a given size K.

[edit] Formal definition

An instance of the hitting set problem consists of:

  • a collection {S1,S2,...,Sn}, where each Si is a subset of T and
  • a positive integer K \le n

The problem is to determine whether there is some subset H of T such that

|H| \le K \and \forall i \in \{1,2,...,n\}: (H \cap S_i) \ne \emptyset.

[edit] NP-complete

The hitting set problem can be proven to be NP-complete by a reduction from the vertex cover problem.

[edit] Proof

Let <G, k> be an instance of the vertex cover problem and G = (V, E). Let T = V and \forall (u, v) \in E add a new set {u,v} to the collection. Now, we show that there is a hitting set H of size k if and only if G has a vertex cover C of size k.

(\Rightarrow) Suppose there is a hitting set H of size k. Since H contains at least one endpoint of each edge, setting C to be H gives a vertex cover of size k.

(\Leftarrow) Suppose there is a vertex cover C for G of size k. For each edge (u,v) either u \in C or v \in C. Setting C to be H gives a hitting set of size k.

Retrieved from "http://en.wikipedia.org../../../h/i/t/Hitting_set.html"