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

Qian Zhou*, Xiaojun Xie, Hua Dai, Weizhi Meng

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

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.

Original languageEnglish
JournalNeural Computing and Applications
Volume34
Pages (from-to)21793–21808
ISSN0941-0643
DOIs
Publication statusPublished - 2022

Keywords

  • Attribute reduction
  • Hypergraph
  • Minimum vertex cover
  • Rough set

Fingerprint

Dive into the research topics of 'A novel rough set-based approach for minimum vertex cover of hypergraphs'. Together they form a unique fingerprint.

Cite this