In this paper, we first establish a Multi-Relation Granular Computing model by a given graph, and point out that all the reducts of the constructed Multi-Relation Granular Computing model are exactly all the minimal vertex covers of the corresponding graph. Thus, the vertex cover problem in graph theory can be converted to the knowledge reduction problem in rough set theory. Based on the conversion, we then introduce methods for dealing with the knowledge reduction problem to solve the vertex cover problem. In particular, we introduce a kind of method called the heuristic reduction algorithm based on entropy.