I'm trying to solve exercise 6.7 on page 150 in "Probability and computing-Randomized algorithms and probabilistic analysis" by Michael Mitzenmacher:
A Hypergraph H is a pair of sets (V,E) where V is the set of vertices and E is the set of hyperedges. Every hyperedge in E is a subset of V. An r-uniform hypergraph is one where the size of each edge is r. A dominating set in a hypergraph is a set of vertices V subset of E such that every edge e intersects S. That is S hits every edge of the hypergraph.
Let H=(V,E) be an r-uniform hypergraph with n vertices and m edges. show that there is a dominating set of size at most (m+n*ln(r))/r. also show that there is a dominating set of size at most [np+((1-p)^r)*m] for every real number 0<=p<=1.
Does anybody have an Idea for a solution? I'm pretty sure it should be solved using the probabilistic method but I'm just really having a hard time of pinpointing a specific solution.
Also if anybody knows of a solution manual for the entire book I'd like a reference please.