Hitting set

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (March 2008)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

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.

1 Formal definition
2 NP-complete
- 2.1 Proof
3 Dual Problem

[edit] Formal definition

An instance of the hitting set problem consists of:

a collection $\{S_1, S_2, \dots, S_n\}$ , where each $S i$ is a subset of $T$ and
a positive integer $K \le |T|$

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

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

[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.

[edit] Dual Problem

Hitting Set is the dual problem of Set Cover. There is one Set Cover set T for every Hitting Set element e and one Set Cover element f for every Hitting Set set S, with f $\in$ T if and only if e $\in$ S.