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

Figure 1

Generalized greedy leaf removal helps us solve the minimum hyperedge cover and the minimum vertex cover problems on hypergraphs. Vertices are represented by dots and hyperedges by circles. The green vertices and hyperedges in (b3) and (c3) are the solution to the MHC or MVC problem, respectively.

Figure 2

The relative size of the core size hypergraphs with Poisson vertex degree distributions, (a),(b) $s_h^v$. (c),(d) $s_v^v$. In (a) and (c) we consider $d$-uniform hypergraphs, meaning that all hyperedge have the same cardinality $d$. In (b) and (d) we consider that the cardinality of the hyperedges follows a Poisson distribution with average cardinality $d$.

Figure 3

Phase diagram of the $h_{\text{core}}$ and $v_{\text{core}}$ percolations on hypergraphs with Poisson vertex degree distributions. The black dots and black line represent the phase boundary of $d$-uniform hypergraphs and hypergraphs with Poisson hyperedge cardinality distribution, respectively. (a) $h_{\text{core}}$. Note that, for the $d$-uniform hypergraph ($d>1$) with Poisson vertex degree distribution, the critical mean degree (i.e., $c^{*}$ of the $v_{\text{core}}$ percolation) can be simply related to $d$ as $c^{*}=e/(d-1)$, where $e=2.71828\cdots$ [see (a) black dots, and Supplemental Material [21] Sec. III C for details]. This result was previously found in Ref. [11]. (b) $v_{\text{core}}$.

Figure 4

(a) Fraction of hyperedges $s_h^h$ (or vertices $s_v^v$) associated with the MHC (MVC) problem for three real-world hypergraphs: APS, DGT, and GMN; and their respective null models computed from Eqs. (5) and (9). This set represents those hyperedges (vertices) that cannot be covered optimally using our generalized GLR procedure. (b) Fraction of vertices $n_h^v$ (hyperedges $n_v^h$) necessary to cover all the hyperedges (vertices) for the three hypergraphs.

Figure 5

Relative size of the core associated with the MDS problem for eleven real-world networks, using the GLR procedure introduced in Ref. [40] (square) and using our generalized GLR approach (circles).