Julien David

Loïck Lhote

Arnaud Mary

François Rioult

Franois Rioult

An average study of hypergraphs and their minimal transversals

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

A hypergraph is a pair H = (V, E) where V = {1, 2, . . . , n} is the set of vertices and E = (E 1 , . . . , E m ) is the collection of hyperedges with E i ⊆ V for all i.

A transversal is a set of vertices that intersects all the hyperedges. A set of vertices X is said to be irredundant if for all vertex i ∈ X, there exists a hyperedge H such that H ∩ X = {i}. X is called a minimal transversal when it transversal and none of its subset is transversal. This is equivalent to being both irredundant and transversal.

Given a hypergraph H, the set of all its minimal transversals forms a hypergraph called the transversal hypergraph.

The Transversal Hypergraph Generation problem (for short, THG-problem) consists in computing the transversal hypergraph of a given hypergraph. In the same way, the associated decision problem (in short, THD-problem) consists in deciding if a first hypergraph H 1 is the transversal hypergraph of a second one H 2 . This problem is known to be equivalent to the famous dualization of monotone boolean functions problem (see [START_REF] Eiter | New results on monotone dualization and generating hypergraph transversals[END_REF]). The Transversal Hypergraph Generation problem appears in very different domains: Artificial Intelligence and Logic [START_REF] Eiter | Identifying the minimal transversals of a hypergraph and related problems[END_REF][START_REF] Eiter | Hypergraph transversal computation and related problems in logic and ai[END_REF], Biology [START_REF] Damaschke | Parameterized enumeration, transversals, and imperfect phylogeny reconstruction[END_REF], Datamining and Machine Learning [START_REF] Gunopulos | Data mining, hypergraph transversals, and machine learning[END_REF], mobile communications [START_REF] Saswati | Hypergraph models for cellular mobile communication systems[END_REF], etc. We refer to [START_REF] Hagen | Algorithmic and Computational Complexity Issues of MONET[END_REF] for a more complete list of applications.

Since a hypergraph may have an exponential number of minimal transversals, the THG-problem does not belong to the class of polynomial problems. However, a long standing question is to decide whether there exists an algorithm to solve THG whose running time is a polynomial on the size of the hypergraph and on the number of minimal transversal. Such an algorithm is called an output-polynomial time algorithm.

The complexity of the THG-problem is closely related to its associated decision problem THD. Precisely, if an output-polynomial algorithm solves THG, then THD can be solved in polynomial time. In addition, THD is clearly in the class of co-NP problems but there is no evidence of its co-NP-completeness. If THD is co-NP-complete, then no output polynomial algorithm is likely to exist for the generation problem THG (unless P=co-NP) [START_REF] Eiter | Identifying the minimal transversals of a hypergraph and related problems[END_REF].

The best known algorithm to generate the transversal hypergraph is quasipolynomial and is due to Fredman and Khachiyan in [START_REF] Michael | On the complexity of dualization of monotone disjunctive normal forms[END_REF]. Its running time is of the form N o(log N ) with N the size of the input plus the output. Nevertheless, this algorithm is not efficient for practical applications. Other algorithmic solutions were proposed and a list of them can be found in [START_REF] Eiter | Computational aspects of monotone dualization: A brief survey[END_REF]. In this article, we focus on the MTMiner algorithm defined by Hébert, Bretto and Crémilleux [START_REF] Hébert | A data mining formalization to improve hypergraph minimal transversal computation[END_REF]. MTMiner is closely related to the mining of the frequent patterns in data mining and is clearly output-exponential in the worst-case. We will study both average complexity and generic-case [START_REF] Kapovich | Generic-case complexity, decision problems in group theory and random walks[END_REF] output-sensitive complexity of the algorithm.

In the previous quoted results, the complexity of the THG-problem and associated algorithms were mostly studied with the worst-case point of view. Indeed, very specific entries were exhibited in order to obtain worst-case lower or upper bounds on the behavior of the algorithms. But these entries do not generally occur in practice, and the existing worst-case analyses are then not sufficient to understand the practical complexity of THG. In this article, we adopt a probabilistic point of view. Though analytic combinatorics is often used to conduct an average study, the symbolic method does not seem to be relevant in our case, as it cannot be used to describe the patterns we are interested in.

The study of random hypergraphs under various distributions is quite common and one of the most popular is the uniform distribution on k-uniform hypergraphs [START_REF] Achlioptas | On the 2-colorability of random hypergraphs[END_REF][START_REF] Dudek | Loose hamilton cycles in random kuniform hypergraphs[END_REF][START_REF] Lelarge | A new approach to the orientation of random hypergraphs[END_REF] (in which all hyperedges have the same cardinal k). In [START_REF] Shmulevich | Almost all monotone boolean functions are polynomially learnable using membership queries[END_REF], the authors prove that under the uniform distribution over all the simple hypergraphs with n vertices, the THG problem is output-polynomial with probability close to 1. In fact under this distribution, the size of the transversal hypergraph is with high probability exponential in n and even the naive algorithm that goes through the whole search space is almost surely output-polynomial. To the best of our knowledge, this is the only study on the average complexity of the THG problem.

In this paper, we consider two random models in which the number n of vertices and the number m of hyperedges are given and suppose that m is a polynomial in n. The results we obtain are original and do not intersect with [START_REF] Shmulevich | Almost all monotone boolean functions are polynomially learnable using membership queries[END_REF].

Section 2 is devoted to the average analysis of patterns in a random hy-pergraph. In Section 2.1, we study a single-parameter model that generalizes the Erdös-Renyi model [START_REF] Erdös | On random graphs[END_REF][START_REF] Erdös | On the evolution of random graphs[END_REF] on graphs and obtain asymptotic estimations on the average number of transversals, irredundants and minimal transversals. In Section 2.2, we make our random model more complex so that the probability that each vertex appears in an hyperedge is given by a function. We identify functions for which the average number of minimal tranversals is at most polynomial, quasi-polynomial or exponential. Section 3 is devoted to algorithms analysis. We study the average complexity of the MTMiner algorithm and the generic-case complexity of the THG-problem. The average complexity of MTMiner is closely related to the average number of irredundants: we obtain upper bounds on the average complexity for both models. Section 4 is devoted to experimental results. Using hypergraphs obtained from real datasets, we discuss the consistency our random models. Conclusion is devoted to perspectives and indications on a random model that might be interesting for a future work.

Pattern analysis

In this section, we study the average properties of hypergraphs under two probabilistic models. For both models we suppose that:

• The number of hyperedges m is at most polynomial in the number of vertices n. Some of our results do not require this supposition and can therefore be extended to cases where m is exponential in n. Moreover, when m = Θ(2 n ), most questions we study in this paper become trivial.

• The probability that a given vertex v appears in a given hyperedge is independent from the probability that a vertex u appears in the same hyperedge or from the probability that v appears in another hyperedge.

• An hypergraph with n vertices and m hyperedges can be seen as a binary matrix M (H) = (m i,j (H)) i=1..m,j=1..n . Each row in the matrix encodes an hyperedge. The value m i,j at line i and column j is equal to 1 if the vertex j belongs to the hyperedge encoded in row i, m i,j = 0 otherwise.

The Single-Parameter Model

Definition 1. HG(n, m, p) random model. The HG(n, m, p) model supposes that the family of random variables (m i,j ) i=1..m,j=1..n forms an independent and identically distributed family of random variables following the same Bernoulli law of parameter p (0 < p < 1).

In this model and in the following results, the reader can consider that p is a constant but announced results are also valid for p depending on n and p > 1e -1 ln n . This bound will be useful in the multiparametric model.

2.1.1. On the average number of transversals.

In the following, T j is the number of transversals of size j on a given hypergraph. Recall that, a given subset X ⊆ V of vertices is a transversal if for all hyperedges H of the hypergraph, there exists at least one vertex v ∈ X such that v ∈ H. We note q = 1p, the probability that a vertex does not appear in a hyperedge and that m is the number of hyperedges in a hypergraph. The probability for a subset X of size j to be a transversal is therefore:

P(X is a transversal) = (1 -q j ) m .
The following results results are obtained by calculations on this probability. {1, . . . , n} We represented the boolean lattice on the set of vertices. As we will show in the following section, according to the size of the subsets, we can estimate the proportion of transversals. Above a given size, we also have a result on the standard-deviation.

∅ log m + ω(1) log m -ω(1) E[T j ] = Θ( n j ) E[T j ] = o( n j ) E[T j ] ∼ n j σ[T j ] = o(E[T j ]) log mp ln n E[T j ] = o(1) log m log m ln n
The first result fixes a bound on the size of transversals. The 1 q in the formula are the basis of the logs. Lemma 1. Let j min = log 1 q m log 1 q m ln n be a value chosen for the purpose of calculus. In the HG(n, m, p) random model, for all j < j min , the average number of transversals E[T j ] tends to 0.

Proof. The following inequalities holds:

E[T j ] = n j
(1q j ) m ≤ n j e -mq j ≤ e jmin ln n-mq j min . Now, the expression in the exponential simplifies into j min ln nmq jmin =ln n × (log 1 q log 1 q m + log 1 q ln n) which tends to -∞. This completes the proof.

The second lemma gives an order of growth for the average number of transversals whose size is at least logarithmic in m. Lemma 2. In the HG(n, m, p) random model, consider j of the form

j = log 1 q m + log 1 q x, x ∈]0, +∞[. 1. if x = Θ(1)
, only a constant proportion of all sets of j vertices is a transversal, i.e., E[T j ] ∼ n j exp(-1/x). 2. if x tends to +∞, almost all sets of j vertices is a transversal, i.e.,

E[T j ] ∼ n j 1 -1 x . 3. if x tends to 0 with x lower bounded by 1/m, almost no sets of j vertices is a transversal, i.e., E[T j ] = o n j .
Proof. Consider a set of vertices X of size j. The probability that X intersects an hyperedge is (1q j ) so that, X is a transversal with probability

P(X is a transversal) = (1 -q j ) m = 1 - 1 mx m for j as in the lemma. If x = Θ(1), we have the equivalence 1 - 1 mx m = exp - m mx + O( 1 mx ) ∼ exp - 1 x .
If x tends to +∞, the previous equivalence remains true and e -1/x ∼ 1 -(1/x).

To conclude if x tends to 0, we have

1 - 1 mx m ≤ exp - m mx = exp - 1 x
which tends to 0.

When j is sufficiently large, the next lemma shows that the standard deviation of T j is negligible compared to its mean. Combined with the Markov inequality, this proves that the number of tranversals of size j is almost surely equivalent to the mean number. This result will be fundamental to obtain an almost sure lower bound on the number of minimal transversals. Lemma 3. In the HG(n, m, p) random model, the standard deviation of the number of transversals of size j with j > log 1

q mp ln n satisfies σ[T j ] = O E[T j ] ln n √ n .
Proof. For any set of vertices X, χ X denotes the random equals to 1 if X is a transversal and 0 otherwise. Consider j ≥ 1. The variance of T j is by definition

V(T j ) = X, Y ⊂ V |X| = |Y | = j P[χ X χ Y = 1] -P[χ X = 1]P[χ Y = 1].
If X and Y are disjoint, the random variables χ X and χ Y are independent and the associated term in the previous sum is zero. We are then led to study non disjoint subsets of vertices. If X and Y are non disjoint, we define I, J and K as

K = X ∩ Y, I = X\Y, J = Y \X,
Note that if X and Y have the same cardinality, then the same is true for I and J . Therefore we note |K| = k and |I| = |J| = jk. The support of K, noted E ⊆ E, is the set of hyperedges that intersect K. If X and Y are transversals, then I and J intersects all the hyperedges of E\E . For a fixed set E , the probability to be K's support is

q k•(m-|E |) (1 -q k ) |E | .
The probability that I and J intersects all the hyperedges of E\E is (1

-q j-k ) m-|E | .
Summing over all the possible cardinalities for E , we obtain

P[χ X = χ Y = 1] = m =0 m (1 -q k ) q k(m-) (1 -q j-k ) 2(m-) = (1 -2q j + q 2j-k ) m
For fixed j and k, there are n k,j-k,j-k possible choices for the sets I, J and K. The probability that X (or Y ) is a transversal is (1q j ) m , and summing over all the possible k, we obtain

V(T j ) = j k=1 n k, j -k, j -k (1 -2q j + q 2j-k ) m -(1 -q j ) 2m .
Various cases are now possible. Case (i). j > log 1 q mn. Then

(1 -2q j + q 2j-k ) m -(1 -q j ) 2m = O 1 n
where the constant term in O only depends on n and not on j. In addition,

j k=0 n k, j -k, j -k = n j 2 so that the variance satisfies V(T j ) = 1 n n j 2 = O 1 n E n [T j ] 2
and the random variable T j is concentrated.

Case (ii). If log 1 q mp ln n ≤ j ≤ log 1 q mn. The variance satisfies the upper bounds

V(T j ) ≤ j k=1 n k, j -k, j -k (1 -2q j + q 2j-k ) m ≤ j k=1 n k, j -k, j -k exp(-2mq j + mq 2j-k ).
Let α k denotes the k-th term of this sum. The ratio of two consecutive α k is upper bounded by

α k+1 α k ≤ j 2 2(n -2j + 2) e mpq 2j ≤ log 2 mn 2(n -2 log mn + 2) e mpq log 1 q ( mp ln n ) 2 ≤ e ln m mp log 2 mn 2(n -2 log 2 mn + 2) = O ln 2 n n
The variance satisfies V(T j ) ∼ α 1 since jα 2 = o(α 1 ), for log 1 q mp ln ln n ≤ j ≤ log 1 q mn. Now, we have

V(T j ) ∼ e -2mq j n 2j-1 (j -1)! 2 ∼ j 2 n E[T j ] 2 .
The result follows for case (ii) and the proof is complete.

To sum up the results on the average number of transversals:

1. almost no subset of size less than log 1 q m log 1 q m ln n are transversal, 2. if the size is log 1 q mω(1), then the number of tranversals is negligible compared to the number of subsets, 3. if the size is equivalent to log 1 q m (up to an additive constant), then almost surely a constant proportion of subsets are transversals. 4. if the size is log 1 q m + ω(1), then almost all subsets are transversals. Intuitively, the set of minimal transversals will mostly be included in cases 2 and 3. Indeed, in case 4, the probability that a given transversal does not contain a subset of case 3 which is also transversal, will intuitively be low.

Average number of irredundants.

A subset X is irredundant if for all vertex i ∈ X, there exists and an hyperedge H such that H ∩ X = {i}. For fixed X of cardinal j , fixed i and H, the probability that H ∩ X = {i} is pq j-1 . For fixed X and H, the probability that i ∈ X such that H ∩ X = {i} is equal to 1jpq j-1 . If X is a irredundant then there exists a tuple (k 1 , . . . , k j ) of positive value where k i is the number of hyperedges H such that H ∩ X = {i} and the probability that X is a irredundant set is equal to:

∀i ≤ j, k i ≥ 1 k 1 + . . . + k j = j ≤ ≤ m m k 1 , . . . , k j (pq j-1 ) • (1 -jpq j-1 ) m-
The next theorem states that the average number of irredundants is quasipolynomial.

Theorem 1. The average number of irredundants in a random model

HG(n, m, p) is O (mn p q 2 log 1 q √ nm) 1 4 (log 1 q nm-log q p-log 1 q log 1 q √ nm)+1
Proof. We study a function that bounds the number of irredundants by considering the following necessary condition: let

X = {x 1 , . . . , x k }, a selection is a set {E 1 , . . . , E k } of hyperedges such that E i ∩ X = {x i } for all i ≤ k. X is a
irredundant set if and only if there exists a selection in the hypergraph.

For each of the n j subsets of size j, if one can find j hyperedges amongst m such that each hyperedge contains one vertex and not the others (the order on hyperedges is not specified), then the condition is satisfied. This occurs with probability pq j-1 j . The average number of irredundants of size j is therefore bounded by the function

f (j) = n j m! (m -j)! pq j-1 j ,
We study the value j for which f (j) is maximal.

f (j + 1) f (j) = (m -j)(n -j) j + 1 pq 2j .
This ratio is decreasing with j. The maximum of h(j) is given by the first integer value of j such that the ratio is smaller than 1.

⇐⇒ q 2j = 1 (m -j)(n -j)p (j + 1) ⇐⇒ j = 1 2 log 1 q (m -j)(n -j) + log 1 q p -log 1 q (j + 1)
It can be proved that with p constant (or p > 1e -1 ln n ) and m large enough, we have log 1 q (m) -1 < log 1 q (mj) ≤ log 1 q (m). The same goes for log 1 q (nj). We bootstrap and simplify:

j ∼ 1 2 log 1 q mn -log q p -log 1 q log 1 q nm
The maximum of the function f is reached for j . We obtain the announced result by computing f (j) (using Stirling's formula) and multiply by n (all possible values for j).

Average number of minimal transversals

In the sequel, M T (resp. M T j ) is the random variable equal to the number of minimal transversals (resp. of size j). It is known that in the worst case, the number of minimal transversals may be exponential with respect to the size of the input hypergraph. However, for the "naive" uniform distribution on hypergraphs, the number of minimal transversal is almost surely at most output linear. As far as we know, the HG(n, m, p) model leads to the first non trivial bound on the average number of minimal transversals, as announced by the next theorem.

O n d(α) log 1 q m+c ln ln m , with d(α) = 1 if α ≤ 1 and d(α) = (α+1) 2 4α otherwise.
Proof. We consider once again a function that bounds the number of minimal transversals. A set X is a minimal transversal if and only if:

1. there exist a selection E for X, 2. for all F ∈ E\E , |F ∩ X| ≥ 1.

The probability that Condition 1 holds is (pq j-1 ) j whereas the probability that Condition 2 holds is (1q j ) m-j . There are n j sets of vertices of size j and each of them have m! (m-j)! possible selections. Then, the average number of minimal transversals of size j is bounded by h(j) with

h(j) = n j m! (m -j)! (pq j-1 ) j (1 -q j ) m-j .
We now determine the j that maximizes h(j). The ratio h(j+1) h(j) satisfies

h(j + 1) h(j) = (m -j)(n -j) j + 1 p 1 -q j q 2j 1 + pq j 1 -q j m-j-1
As in the previous section, this ratio is also decreasing. Two cases are now possible according to the value of α. Case α ≤ 1. h(j) is maximized by j min with:

• j min = log 1 q m(1-α)
p ln m when α < 1,

• j min = log 1 q mp ln ln m when α = 1.

Precisely, for some real x > 0 (resp. x < 0), the ratio h(j min +1+x)/h(j min +x) tends to 0 (resp. +∞) when n grows so that the average number of minimal transversals satisfies

E[M ] ≤ n j=1 h(j) = O(h(j min + 1)).

Now, asymptotic computations give

h(j min ) = exp ln n log 1 q m + O(ln m ln ln m)
which completes the proof in case α ≤ 1.

Case α > 1. Consider j min = 1 2 log 1 q mn -1 2 log 1 q ln m. Note that j min may not maximize h(j) but if x tends to +∞ (resp. -∞) with |x| = O(ln ln ln m), the ratio h(j min + 1 + x)/h(j min + x) tends to 0 (resp. +∞). Then, the average number of minimal transversals satisfies The result follows from the fact that max |j-jmin|≤ln ln ln m h(j) = exp d(α)ln n log 1 q m + O(ln m ln ln m) .

E[M ] ≤ n j=1 h(j) ∼

Almost sure lower bound for the number of minimal transversals

A generic lower bound of a random variable (i.e. a lower bound which is true with probability close to 1) is often obtained by studying the moments of higher order or the variance. We did not succeed in studying the higher moments of the number of minimal transversals. However, we relate the number of minimal transversals to the number of transversals and use the concentration property given in Lemma 3.

The number M T of minimal transversals is lower bounded by M j , the number of minimal transversals of size j. Among the T j transversals of cardinal j, M T j are irredundant and T j -M T j are supersets of transversals of cardinal j -1. By definition, there are T j-1 transversals with cardinal j -1 and each of these transversals can be completed in at most nj + 1 transversals of cardinal j. We deduce the inequalities

M T ≥ M T j and T j -(n -j + 1)T j-1 ≤ M T j ≤ T j . (1)
The lower bound entails that for all 0 < < 1,

P(M T j ≤ E[T j ]) ≤ P(T j -(n -j + 1)T j-1 ≤ E[T j ]) P(M T j < E[T j ]) ≤ P(T j-1 < E[T j-1 ])+P (T j < (E[T j ] + (n -j + 1)E[T j-1 ])) .
Consider l = log 1 q mp ln n + 1 (in order to use Lemma 3) . We have

E[T l ] + (n -l + 1)E[T l-1 ] = E[T l ] 1 + O ln n n
and the Bienaymé-Tchebychev Inequality with Lemma 3 lead to the following proposition.

Proposition 1. Consider with 0 < < 1. In the random model HG(n, m, p), the number M T of minimal transversals satisfies

P(M T < E[T l ]) = O ln 2 mn (1 -) 2 n
where T l is the set of transversals of size l = log 1 q mlog 1 q ln n + log 1 q p q . Corollary 1. In the random model HG(n, m, p), the number of minimal transversals is almost surely greater than

n log 1 q m+O(ln ln m)
Proof. The idea is to compute E[T l ] and use Lemma 3.

Multiparametric Model

In this section, we no longer consider that the vertices occur in an hyperedge with the same probability. As we will show in Section 4, this is much more consistent with real-case datasets.

Definition 2 (HG(n, m, g) random model). A hypergraph H with n hyperedges and m vertices is seen as a binary matrix M (H) = (m i,j (H)) i=1..m,j=1..n . The HG(n, m, g) model supposes that the family of random variables (m i,j ) i=1..m,j=1..n forms an independent family of random variables. In addition, for all i, j, the random variable m i,j follows a Bernoulli law of parameter p i = g(i) (and

q i = 1 -g(i)) with g : N → [0, 1]}.
We partition the set V into 3 subsets:

• The set U of ubiquitous vertices. Let x be a fixed constant. For all vertices u ∈ U , we have that q u < x m with q u = 1p u . • The set R of rare events. For all vertices r ∈ R, we have that p r < 1e -1 ln n . Note that this implies that p r < 1 ln n . The latter bound slowly tends to zero and is relevant on experimental data (see Section 4), the former simplifies calculus.

• The set O of other events, that is O = V \ {U ∪ R}.

We mainly use this decomposition to study the average number of minimal transversals in the HG(n, m, g) model.

A lower bound on the average number of transversals

In the HG(n, m, g) model, let µ the average value of the random variables q i . In other words:

µ = n i=1 q i n Lemma 4.
In the HG(n, m, g) model, the average number of transversals is

Ω (2 n -m(1 + µ) n ).
Proof. The average number of transversals is given by the following formula:

E[T ] = n j=0 X⊂V |X|=j (1 - i∈X q i ) m .
Using the Bernoulli inequality, we have:

E[T ] ≥ n j=0 X⊂V |X|=j (1 -m i∈X q i ) ≥ 2 n -m n j=0 X⊂V |X|=j i∈X q i = 2 n -m n i=1 (1 + q i )
Then, according to the geometric inequality we have n i=1

(1 + q i ) ≤ n i=1 1 + q i n n and therefore E[T ] ≥ 2 n -m(1 + µ) n
which concludes the proof.

Corollary 2. The average number of irredundants (and then minimal transversals) is bounded by O(mn(1 + µ) n ).

Proof. From Lemma 4 we obtain an upper bound on the average number of subset that are not transversals, that is to say O(m(1 + µ) n ). In the worst case, all those sets are irredundant and if we add any vertex to one of those subsets, it becomes a minimal transversal.

Although this is not precise, it has a certain advantage: starting from a complex model with a large number of parameters, we now have an estimation that relies on only 3 parameters. It can also be easily interpreted: if µ tends to 0 then almost all vertices appears in almost all hyperedges, hyperedges are all similar. In this case, there is few minimal transversals. If µ tends to 1 then almost each vertex appears in few hyperedges, hyperedges are all really different, that is to say the pairwise intersection of hyperedges is always small and there is an exponential number of minimal transversals. Proof. In order to obtain an upper bound, we use the result in Theorem 1. In the HG(n, m, p) model, the upper bound on the average number of irredundants decreases as p increases. Recall that for all vertices a ∈ O∪U , we have p a ≥ 1e -1 ln . The average number of irredundants in the HG(n, m, 1-e -1 ln ) model is an upper bound of the average number of irredundants containing only vertices in

On the average number of irredundants

O. If q = e -1
lnn , for all y we have log 1/q y = ln y ×ln n. Using this simplification, we obtain the announced upper bound.

Let Irr j,l be the number of irredundants of size j containing exactly l rare vertices. We have:

Irr j,l ≤ Irr j-l,0 × Irr l,l
where Irr j-l,0 is exactly the number of irredundants containing only vertices in O ∪ U and Irr l,l is the number of irredundants containing only vertices in R. Note that Lemma 5 gives an upper bound on Irr j-l,0 . We obtain a bound on Irr l,l by adapting the function f (j) from Section 2.1.2. Since for all vertices r ∈ R, we have p < 1e -1 ln n < 1 ln n , we have:

Irr j,l ≤ |R| l m! (m -l)! 1 ln n l Irr j-l,0
Now we obtain an upper bound on the average number of irredundant in the HG(n, m, g) model.

Irr j = min{j,|R|} l=0 |R| l m ln n l Irr j-l,0
From this formula, it can be deduced that if |R| is not to large in the size of n, then the average number of irredundants is at most quasi-polynomial. Lemma 6. In the HG(n, m, g) model, if |R| = O((ln n) c ) where c is a constant, then the number of irredundants is quasi-polynomial.

Proof. From Lemma 5, we know that Irr j-l,0 is at most quasi-polynomial. Since

l = O(|R|) = O((ln n) c ), it is clear that |R| l m ln n l is also quasi-polynomial.
Lemma 7. In the HG(n, m, g) model, the probability to have a polynomial number of irredundants containing ubiquitous vertices tends to 1.

Proof. Let Irr(H) denote the set of irredundants of an hypergraph H. For a fixed vertex e ∈ V , let Irr(H, e) the set of irredundants containing e. Let N (e) be the set of hyperedges not containing the vertex e. We have:

Irr(H, e) ⊆ {X ∪ {e} | X ∈ Irr(N (e))}.
Hence we have:

|Irr(H, e)| ≤ |Irr(N (e))|,
that is to say the number of irredundants containing a given vertex e is bounded by the number of irredundants of the hypergraph reduced to the hyperedges that do not contain e. The number of hyperedges that do not contain an ubiquitous vertex is bounded by x and using Poisson paradigm we know that in a random hypergraph an ubiquitous vertex is in at least mx √ x hyperedges with probability tending to 1. The number of irredundants of an hypergraph with at most x √ x hyperedges is polynomial since x is a constant.

On the average number of minimal transversals.

Recall that M denotes the number of minimal tranversals. Since the upper bounds obtained in Lemma 6, 5 and 7 also holds for minimal transversals, we obtain the following theorem. Theorem 3. In the HG(n, m, g) model, we have the following:

• If |O ∪ R| = O(ln n), then E[M ] is at most polynomial. • If |R| = O((ln n) c ) where c is a constant, then E[M ] is at most is quasi- polynomial. • If |R| = Θ(n) , then E[M ] is at most exponential on |R|.
The first point comes from Lemma 7 and the fact that the number of minimal transversals of a set of size c ln n is n c .

Algorithm analysis

In this section we study the average complexity of the MT-Miner Algorithm. The worst-case input complexity of this algorithm is a polynomial in n times the number of irredundants. The analysis we perform and the results we obtain is also valid on any algorithm whose search space is bounded by the set of irredundants: Apriori, Dong-Li algorithm [START_REF] Dong | Mining border descriptions of emerging patterns from dataset pairs[END_REF], Kavvadias-Stravropoulos [START_REF] Kavvadias | An efficient algorithm for the transversal hypergraph generation[END_REF], Uno-Murakami [START_REF] Murakami | Efficient algorithms for dualizing large-scale hypergraphs[END_REF]. . . Here Supp H (W ) is the number of hyperedges that intersect W .

Input: an hypergraph H with n hyperedges

Output: the minimal tranversals of H M T := {{v}| v ∈ V, |Supp H ({v})| = m} N 1 := {{v}| v ∈ V, n > Supp H ({v}) = ∅} j = 1 While N j = ∅ do for all prefix V with V ∪ {v 1 } and V ∪ {v 2 } in N j × N j do W = V ∪ {v 1 } ∪ {v 2 } if W is irredundant then if Supp H (W ) = n then add W to M T else add W to N j+1 end if end if end for j=j+1 end While return M T .

Average complexity of the MT-Miner Algorithm.

The MTMiner algorithm was described by Hébert, Bretto and Crémilleux in [START_REF] Hébert | A data mining formalization to improve hypergraph minimal transversal computation[END_REF]. The algorithm computes all the minimal transversals of a given hypergraph using a levelwise strategy. Precisely at the j th level, the algorithm computes the irredundants formed with j vertices. Among the irredundants, some are minimal tranversals and are stored in a data structure. The others are not minimal transversals but they might be part of one and they are used to build irredundants of size j + 1.

Each irredundant of size j can be extended in at most nj sets of size j + 1 and the minimality of each candidate set can be tested in polynomial time (w.r.t. the input size). MTMiner uses a prefix tree to optimize this generation step but even with the naive method (generate all the possible extensions), the complexity of MTMiner is O(Poly(m, n)N ) where N is the number of irredundants.The algorithm is described in Figure 3.1.

A non trivial upper bound on the average complexity of MTMiner follows from Theorem 1.

Proposition 2. In the HG(n, m, p) model, there exist some positive constant c such that the average complexity of MTMiner is

O (mn log 1 q √ nm p q 2 ) 1 4 (log 1 q nm-log q p-log 1 q log 1 q √ nm)+c .
An equivalent result can be obtained in the HG(n, m, g) model using Lemma 6.

Proposition 3. In the HG(n, m, g) model, if |R| = O((ln n) c ) where c is a constant, then the average input-complexity of MTMiner is at most quasipolynomial.

Since MTMiner generates at least all the minimal transversals, its complexity is lower bounded by M . The generic lower bound given by Proposition 2 entails a generic lower bound on the complexity of MTMiner.

Generic-case complexity of the THG-problem

The notion of generic-case complexity is defined in [START_REF] Kapovich | Generic-case complexity, decision problems in group theory and random walks[END_REF]. The idea is to study the worst-case complexity of an algorithm on a generic-subset of inputs. In a given random model, a subset E of inputs is said to be generic if the probability that a random input is in E tends to 1. The study of generic complexity is particularly interesting when no polynomial method is known to solve a problem in the general case (N P -complete problems, undecidable problems [START_REF] Myasnikov | Generic complexity of undecidable problems[END_REF]), whereas there seem to be efficient methods in practice. The theoretical complexity of the THG-problem was discussed in the introduction. In particular, it is not known whether the problem is output-polynomial in the worst-case. The following theorem states that with probability that tends to 1 in the single-parameter model, the algorithm MTMiner is output-polynomial. In other words, the set of inputs for which the algorithm is output-polynomial is a generic set. Proof. To simplify the notations, we write γ = + (α+1) 2 4α and a = 1 2 E[T j ] with j as in Proposition 1. We have

P(D > M γ ) = P([D > M γ ] ∩ [M < a]) + P([D > M γ ] ∩ [M ≥ a]) ≤ P(M < a) + P(D ≥ a γ ) = O ln 2 mn n + E[D] a γ
Alternative expressions for a γ and E[D] are

E[D] = n (α+1) 2 4α log 1 q m+O(ln ln m) , a γ = n ( + (α+1) 2 4α
) log 1 q m+O(ln ln m) .

In particular, E

[D]/a γ is O(n -2 log 1 q m ) when γ > + (α+1) 2 4α
and the O-term tends to 0. This completes the proof.

Comparison with real data

The following benchmark were made using datasets from the Frequent Itemset Mining Dataset Repository1 , that are often used by the datamining community. The experimental results that we exhibit might therefore be well known by specialists. The objective of this section is to exhibit the links between real datasets and our probabilistic models.

We only present a selection of experimental results, that is already able to capture the diversity of hypergraphs in various contexts. It is important to note that for each example presented in this paper, one can find several datasets satisfying the same properties.

From Figure 3 to Figure 6, the histograms on the left side represent the number of hyperedges in which each vertex appears. Vertices are sorted according to the decreasing order of the number of hyperedges in which they appear. Histograms on the right side represents the size of hyperedges in each hypergraph.

• mushroom.dat: contains a few ubiquitous vertices and a few rare vertices.

All the hyperedges have the same size. Those kinds of datasets validate the choice of most study to focus on k-uniform hypergraphs.

• accident.dat: contains a few ubiquitous vertices and a lot of rare vertices. The size of hyperedges seems to follow a Gaussian distribution.

• pumsbstar.dat: does not contain ubiquitous vertices and most vertices are rare.

• T10I4D100K.dat: all vertices are rare. Again, the size of hyperedges seems to follow a Gaussian distribution.

Our probability models seem to be more appropriate on the second and the fourth example, as the size of the hyperedges seems to follow a Gaussian distribution.

In our experiments, the generation of the minimal transversals were efficient on databases that have similar distribution to mushroom.dat. This result comforts us in the belief that the presence of rare events is the main parameter (by opposition to being just an important parameter amongst others) to decide whether the number of the minimal transversals is going to explode. Figure 7 shows the distribution of the minimal transversals in mushroom.dat. As we can see, the number of minimal transversals T min,j of a given size j is maximal when j = 16 and T min,16 ∼ 6 × 10 6 . Using the model H(n, m, g) and Theorem 3, we could foretell that in cases accidents.dat, pumsbstar.dat, T10I4D100K.dat the number of minimal transversals explodes, which seems indeed to be the case. Even after a long time execution (more than a week) on a regular computer, only a small proportion of the search space had been visited, whereas the number of minimal transversals was tremendously huge. We also tried to write the

Conclusion

The models we have studied already give a partial information on the average number of minimal transversals in real context and on the average complexity of the algorithms. Indeed, our models predict the order of growth of the size of minimal transversals. Hence, we are able to tell whether the computation can be made in reasonable time and space. Though, the upper bounds we have obtained on the number of minimal transversals still seems too large compared to real-data examples.

Figure 1 :

 1 Figure 1:We represented the boolean lattice on the set of vertices. As we will show in the following section, according to the size of the subsets, we can estimate the proportion of transversals. Above a given size, we also have a result on the standard-deviation.

Theorem 2 .

 2 Consider the random model HG(n, m, p) with m = βn α , β > 0 and α > 0. There exist a positive constant c := c(α, β, p) such that the average number of minimal transversals is

jmin+ln

  ln ln m j=jmin-ln ln ln m h(j) = O ln ln ln m max |j-jmin|≤ln ln ln m h(j) .

Lemma 5 . 1 4

 51 The average number of irredundants containing only vertices in O ∪ U is O((nm ln √ nm) ln n(ln nm-2 ln ln n-ln ln √ mn) )

Figure 2 :

 2 Figure 2: The MTMiner-algorithm. Here Supp H (W ) is the number of hyperedges that intersect W .

Theorem 4 .

 4 Consider the random model HG(n, m, p) with m = βn α , β > 0 and α > 0. Under this model, the generic complexity of the THG-problem is output-polynomial. Precisely, there exist an algorithm (MTMiner) such that for all > 0, the algorithm computes the minimal tranversals of an input hypergraph in time M + (α+1) 2 4α with probability asymptotically 1 and where M is the number of minimal transversals.

Figure 3 :Figure 4 :

 34 Figure 3: mushroom.dat (119 vertices, 8124 hyperedges)

Figure 5 :Figure 6 :Figure 7 :

 567 Figure 5: pumsbstar.dat (7116 vertices, 49046 hyperedges)

http://fimi.ua.ac.be/data/