TY - JOUR
T1 - A novel rough set-based approach for minimum vertex cover of hypergraphs
AU - Zhou, Qian
AU - Xie, Xiaojun
AU - Dai, Hua
AU - Meng, Weizhi
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer-Verlag London Ltd., part of Springer Nature.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - Attribute reduction
KW - Hypergraph
KW - Minimum vertex cover
KW - Rough set
U2 - 10.1007/s00521-022-07620-8
DO - 10.1007/s00521-022-07620-8
M3 - Journal article
AN - SCOPUS:85135313791
SN - 0941-0643
VL - 34
SP - 21793
EP - 21808
JO - Neural Computing and Applications
JF - Neural Computing and Applications
ER -