  A hitting set for a collection of sets is a set that has a non-empty
intersection with each set in the collection; the hitting set problem is to
find a hitting set of minimum cardinality. Motivated by instances of the
hitting set problem where the number of sets to be hit is large, we introduce
the notion of implicit hitting set problems. In an implicit hitting set problem
the collection of sets to be hit is typically too large to list explicitly;
instead, an oracle is provided which, given a set H, either determines that H
is a hitting set or returns a set that H does not hit. We show a number of
examples of classic implicit hitting set problems, and give a generic algorithm
for solving such problems optimally. The main contribution of this paper is to
show that this framework is valuable in developing approximation algorithms. We
illustrate this methodology by presenting a simple on-line algorithm for the
minimum feedback vertex set problem on random graphs. In particular our
algorithm gives a feedback vertex set of size n-(1/p)\log{np}(1-o(1)) with
probability at least 3/4 for the random graph G_{n,p} (the smallest feedback
vertex set is of size n-(2/p)\log{np}(1+o(1))). We also consider a planted
model for the feedback vertex set in directed random graphs. Here we show that
a hitting set for a polynomial-sized subset of cycles is a hitting set for the
planted random graph and this allows us to exactly recover the planted feedback
vertex set.
