The minimum vertex cover problem is a classical combinatorial optimization problem. This paper studies this problem based on rough sets. We show that finding the minimal vertex cover of a graph can be translated into finding the attribute reduction of a decision information table. At the same time, finding a minimum vertex cover of graphs is equivalent to finding an optimal reduct of a decision information table. As an application of the theoretical framework, a new algorithm for the minimum vertex cover problem based on rough sets is constructed. Experiments show that the proposed algorithm gets better performance in terms of the ratio value when compared with some other algorithms.