  Covering problems are classical computational problems concerning whether a
certain combinatorial structure 'covers' another. For example, the minimum
vertex covering problem aims to find the smallest set of vertices in a graph so
that each edge is incident to at least one vertex in that set. Interestingly,
the computational complexity of the minimum vertex covering problem in graphs
is closely related to the core percolation problem, where the core is a special
subgraph obtained by the greedy leaf removal procedure. Here, by generalizing
the greedy leaf removal procedure in graphs to hypergraphs, we introduce two
generalizations of core percolation in graphs to hypergraphs, related to the
minimum hyperedge cover problem and the minimum vertex cover problem on
hypergraphs, respectively. We offer analytical solutions of these two core
percolations for random hypergraphs with arbitrary vertex degree and hyperedge
cardinality distributions. We also compute these two cores in several
real-world hypergraphs, finding that they tend to be much smaller than their
randomized counterparts. This result suggests that both the minimum hyperedge
cover problem and the minimum vertex cover problem in those real-world
hypergraphs can actually be solved in polynomial time. Finally, we map the
minimum dominating set problem in graphs to the minimum hyperedge cover problem
in hypergraphs. We show that our generalized greedy leaf removel procedure
significantly outperforms the state-of-the-art method in solving the minimum
dominating set problem.
