Lower and upper bounds on the cardinality and the number of irreducible partial covers for almost all set cover problems are obtained. These bounds allow us to prove that there is no polynomial algorithm which for almost all set cover problems constructs all irreducible partial covers, but there exists a totally polynomial algorithm which constructs all irreducible partial covers for almost all set cover problems.
- Computational complexity
- Irreducible partial cover
- Totally polynomial algorithm
ASJC Scopus subject areas
- Computational Theory and Mathematics