Covering Problems and Core Percolations on Hypergraphs

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 vert...

Full description

Saved in:
Bibliographic Details
Published in:Physical review letters 2020-06, Vol.124 (24), p.1-248301, Article 248301
Main Authors: Coutinho, Bruno Coelho, Wu, Ang-Kun, Zhou, Hai-Jun, Liu, Yang-Yu
Format: Article
Language:English
Subjects:
Exact solutions
Graph theory
Graphs
Percolation
Polynomials
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0031-9007
1079-7114
DOI:10.1103/PhysRevLett.124.248301