A novel rough set-based approach for minimum vertex cover of hypergraphs

Minimum vertex covering has been widely used and studied as a general optimization problem. We focus on one of its variation: minimum vertex cover of hypergraphs. Most existed algorithms are designed for general graphs, where each edge contains at most two vertices. Moreover, among these algorithms, rough set-based algorithms have been proposed recently and attract many researchers sight. However, they are not efficient enough when the number of nodes and hyperedges scale largely. To address these limitations, we propose a novel rough set-based approach by combining rough set theory with the stochastic local search algorithm. In this approach, three improvements have been introduced, i.e., (1) fast relative reduct construction method, which can quickly achieve a relative reduct, and it is based on low-complexity heuristics; (2) (p, q)-reverse incremental verification mechanism, which uses incremental positive region update technology to quickly verify whether a required attribute pair can be found; (3) adjusting iterative process rules, the main purposes of these rules are avoiding repeated computation and jumping out of local optimum. Finally, by comparing groups of benchmark graphs and hypergraphs with the existing algorithms based on rough sets, experimental results presents the advantages and limitations of our proposed approach.