The set covering problem (SCP) is a classical NPhard problem in operation research and computer science.A SCP was transformed into an equivalent bipartite graph (BG） and an upperlower bound algorithm for SCP or BG was proposed.Some mathematical properties of SCP or BG were presented which can decrease the size of the problem and can speed up the algorithm.A new reduction algorithm for SCP was proposed by combining the mathematical properties with the upperlower bound algorithm.Then the worstcase time complexity of the new reduction algorithm was analysed.The reduction algorithm proposed can be used alone,or cooperating with other algorithms to get more effective results.Several instances were solved and analyzed to illustrate the principles and applications of the algorithm.