Covering Problems and Core Percolations on Hypergraphs
Coutinho, B.
; Wu, A.-K.
; Hai-Jun, H.
; Liu, Y.-Y. L.
Physical Review Letters Vol. 124, Nº 24, pp. 248301 - 248306, June, 2020.
ISSN (print): 0031-9007
ISSN (online): 1079-7114
Scimago Journal Ranking: 3,69 (in 2020)
Digital Object Identifier: 10.1103/PhysRevLett.124.248301
Abstract
We introduce two generalizations of core percolation in graphs to hypergraphs, related to the minimum hyperedge cover problem and the minimum vertex cover problem on hypergraphs, respectively. We offer analytical solutions of these two core percolations for uncorrelated random hypergraphs whose vertex degree and hyperedge cardinality distributions are arbitrary but have nondiverging moments. We find that for several real-world hypergraphs their two cores tend to be much smaller than those of their null models, suggesting that covering problems in those real-world hypergraphs can actually be solved in polynomial time.
