info prev up next book cdrom email home

Hitting Set

Let $S$ be a collection $S$ of subsets of a finite set $X$. The smallest subset $Y$ of $X$ that meets every member of $S$ is called the hitting set or Vertex Cover. Finding the hitting set is an NP-Complete Problem.

© 1996-9 Eric W. Weisstein