Effect of Cardinality and Frequency Restrictions on the Hitting Set and Vertex Cover Problems

Abstract

The Hitting Set problem is investigated in relation to restrictions imposed on the cardinality of subsets and the frequency of element occurences in the subsets. It is shown that the Hitting Set subproblem where each subset has cardinality $C$ for fixed $C\ge 2$ and the frequency of each element is exactly $f$ for fixed $f\ge 3$ remains NP-complete, but the problem becomes polynomial when $f\le 2$. The restriction of the Vertex Cover problem to $f$-regular graphs for $f\ge 3$ remains NP-complete.