The relationship between attribute reducts in rough sets and minimal vertex covers of graphs

The problems to find attribute reduction in rough sets and to obtain the minimal vertex cover for graphs are both NP-hard problems. This paper studies the relationship between the two problems. The vertex cover problem for graphs from the perspective of rough sets is first investigated. The attribute reduction of an information system is then studied in the framework of graph theory. The results in this paper show that finding the minimal vertex cover of a graph is equivalent to finding the attribute reduction of an information system induced from the graph. Conversely, the attribute reduction computation can be translated into the calculation of the minimal vertex cover of a derivative graph. Finally, a new algorithm for the vertex cover problem based on rough sets is presented. Furthermore, experiments are conducted to verify the effectiveness of the proposed method.