Covering Problems and Core Percolations on Hypergraphs

Abstract

Covering problems are classical computational problems concerning whether a certain combinatorial structure 'covers' another. For example, the minimum vertex covering problem aims to find the smallest set of vertices in a graph so that each edge is incident to at least one vertex in that set. Interestingly, the computational complexity of the minimum vertex covering problem in graphs is closely related to the core percolation problem, where the core is a special subgraph obtained by the greedy leaf removal procedure. Here, by generalizing the greedy leaf removal procedure in graphs to 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 random hypergraphs with arbitrary vertex degree and hyperedge cardinality distributions. We also compute these two cores in several real-world hypergraphs, finding that they tend to be much smaller than their randomized counterparts. This result suggests that both the minimum hyperedge cover problem and the minimum vertex cover problem in those real-world hypergraphs can actually be solved in polynomial time. Finally, we map the minimum dominating set problem in graphs to the minimum hyperedge cover problem in hypergraphs. We show that our generalized greedy leaf removel procedure significantly outperforms the state-of-the-art method in solving the minimum dominating set problem.

References in corpus (7)

• Critical phenomena in complex networks
• Random hypergraphs and their applications
• Core percolation on complex networks
• Finite size scaling for the core of large random hypergraphs
• Academic team formation as evolving hypergraphs
• Statistical Mechanics of the Minimum Dominating Set Problem
• Critical random hypergraphs: The emergence of a giant set of identifiable vertices

Cited by in corpus (12)

• Higher-order percolation processes on multiplex hypergraphs
• Hypergraph reconstruction from network data
• Predicting the Future of AI with AI: High-quality link prediction in an exponentially growing knowledge network
• The theory of percolation on hypergraphs
• Higher-Order Components Dictate Higher-Order Contagion Dynamics in Hypergraphs
• Hypergraphx: a library for higher-order network analysis
• Clifford-deformed Surface Codes
• The nature of hypergraph $k$-core percolation problems
• $(k,q)$-core decomposition of hypergraphs
• Complex hypergraphs
• Modeling temporal hypergraphs
• A local algorithm and its percolation analysis of bipartite $z$-matching problem