<figure><img src="image_1.png" /></figure>

HAL
open science

# On the average complexity of Berge Algorithm

Julien David, Mostafa Gholami, Loïck Lhote

► To cite this version:

Julien David, Mostafa Gholami, Loïck Lhote. On the average complexity of Berge Algorithm. 2025. [hal-04637413](https://hal.science/hal-04637413v1)

HAL Id: hal-04637413

https://hal.science/hal-04637413v1

Preprint submitted on 21 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the average complexity of Berge Algorithm

Julien David ☑

CNRS NormaSTIC FR 3638, France

Normandie University, UNICAEN, ENSICAEN, CNRS, GREYC, Caen, France

Mostafa Gholami ☑

CNRS NormaSTIC FR 3638, France

Normandie University, UNICAEN, ENSICAEN, CNRS, GREYC, Caen, France

Loick Lhote ☑

CNRS NormaSTIC FR 3638, France

Normandie University, UNICAEN, ENSICAEN, CNRS, GREYC, Caen, France

## Abstract

Given a hypergraph, computing its transversal hypergraph is a classical problem whose exact worst-case complexity is still unknown today. In this article, for random hypergraph models à la Erdos and Renyi, we compute the average number of minimal transversals. We also study the average complexity of Berge's algorithm, which sequentially enumerates the minimal transversals. We prove that the average complexity of Berge is quasi-linear in the average number of minimal traverses. Our contribution is also methodological: we use a wide range of analytic combinatorics techniques to extract the coefficients of probabilistic generating functions.

2012 ACM Subject Classification Design and analysis of algorithms

**Keywords and phrases** Average Complexity, Minimal Transversal, Berge Algorithm, Hypergraphs, Analytic Combinatorics

Digital Object Identifier 10.4230/LIPIcs...

## 1 Introduction

A hypergraph $\mathcal{H}$ is a pair $(\mathcal{V}, \mathcal{E})$ where $\mathcal{V}$ is a set of vertices and $\mathcal{E}$ is a set of hyperedges, each hyperedge being a subset of $\mathcal{V}$. A transversal of $\mathcal{H}$ is a subset of vertices $T \subseteq \mathcal{V}$ that intersects all the hyperedges. A transversal is said minimal if no proper subset is also a transversal. The Transversal Hypergraph Generation problem (THG problem) consists in computing, for a given hypergraph $\mathcal{H}$, the transversal hypergraph $\text{Tr}(\mathcal{H})$ formed with all the minimal transversals of $\mathcal{H}$.

This problem has gained considerable attention in recent years due to its generality and wide applicability in a variety of fields, including artificial intelligence and logic [16], computational biology [10, 36, 26], cryptography [32], database theory [37], data mining [23, 1, 7], distributed computing [21], e-commerce [3], machine learning [24], mathematical programming [35, 33], mobile communication systems [39], semantic web [30], topology [14], combinatorics [38], and game theory [8].

Several problems are equivalent to the THG problem. For instance, the enumeration of minimal dominating sets or total dominating sets in graphs can be polynomially reduced to the THG problem [9, 29].

The size of $\text{Tr}(\mathcal{H})$, or equivalently, the number of minimal transversals, may be exponential in the size of $\mathcal{H}$. Efforts have been done to determine an upper bound for the size of $\text{Tr}(\mathcal{H})$ such as in [4] (and the references it contains) where both upper and lower bounds have been computed for tripartite 3-uniform hypergraphs. Since the size of $\text{Tr}(\mathcal{H})$ may be exponential in the size of $\mathcal{H}$, it is not possible to find an algorithm that runs in polynomial-time. Johnson, Yannakakis and Papadimitriou [28] introduced various classes of complexity involving the
XX:2 On the average complexity of Berge Algorithm

size of the intermediate results or the size of the output. They defined the class of output-
polynomial time problems that can be solved in polynomial time with respect to the size of
the input and the output.

Finding an *output-polynomial* algorithm for Transversal Hypergraph Generation is a
long-standing problem [12]. While the question remains open for arbitrary hypergraphs,
algorithms achieving output polynomial time complexity exist for several classes of hyper-
graphs: hypergraphs with bounded minimal transversals [15], with bounded edge sizes [6, 15],
of bounded degree [17], of bounded-edge intersections, of bounded conformality [6].

The Berge algorithm, also known as the sequential method, was the first proposed
algorithm to solve the THG problem [5]. It computes the transversal hypergraph by adding
one by one the hyperedges and by updating the set of minimal transversals. Takata proved
that its worst-case complexity is not output-polynomial [40] and exhibited specific hypergraphs
where the quantity of intermediate minimal transversals could exponentially exceed the final
solution. In recent years, several improvements of the Berge algorithm have been conducted.
As instances, we can cite the algorithms proposed by Dong and Li [13], Bailey, Manoukian,
and Ramamohanarao [2], Kavvadias and Stavropoulos [31]. Using a method akin to Takata’s
in [40], Hagen proved that most of the improvements of Berge algorithms that mentioned
are not output polynomial [25].

The currently fastest known algorithm for solving the Transversal Hypergraph Generation
problem is due to Fredman and Khachiyan [20, 34] and runs in quasip polynomial time N<sup>o(log N)</sup>,
where N is the size of the input plus the output.

In this paper, we adopt a probabilistic point of view on the **THG** problem and we are
interested in computing the average size of the output and the average case complexity of the
algorithms. In [22], the authors studied the average-case complexity of the decision version
of the **THG** problem on uniform instances. However, the uniform distribution leads with high
probability to very specific hypergraphs. An upper bound on the average complexity of
the **MTMiner** algorithm [27] for the **THG** problem, is also given in [11]. The authors study
various random models in which they give bounds on the number of transversals or minimal
transversals. Then they use those results to obtain bounds on the average complexity of the
**MTMiner** algorithm.

In this article, we use the probabilistic models introduced in [11] (see Section 2). However,
our methodology based on Analytic Combinatorics [19] is for the first time used in the
analysis of minimal transversals. The methodology allows us obtain more precise results, in
particular an equivalence on the asymptotic average number of minimal transversals. We
also study the average-case behaviour of Berge algorithm instead of MTMiner.

Analytic Combinatorics is a general method developed by Flajolet and Sedgewick in the
80's [19]. The method mixes tools from the Symbolic Method and complex analysis in order
to describe the asymptotic behavior of algorithms or large random data structures.

The main tools are generating functions whose coefficients describe the probabilistic
behavior of the parameters of interest. Explicit expressions of the generating functions are
usually obtained using the Symbolic Method that translates the combinatorial structure of
the problem into operations on the generating functions. Then, tools from complex analysis
such as transfer theorems or saddle point method are used to compute the asymptotic of the
coefficients.

Paper is organized as follows. Section 2 details random models we consider on hypergraphs.
Section 3 recall basic definitions and notations on hypergraphs and Berge Algorithm. We
also show the relation between the probability of a given set to be a minimal transversal and
the average case complexity of Berge algorithm. Section 4 describe probabilistic generating
functions for a set with $\ell$ vertices to be a minimal transversal in the general model. As we will see, both an exponential generating function and an ordinary one will be necessarily to obtain the average complexity of Berge Algorithm. Section 5 contains the main results of the paper. We present the probability for a given set of size $\ell$ to be a minimal transversal in an hypergraph with $m$ hyperedges. From this we deduce the average number of minimal transversal and the average complexity of Berge algorithm. Finally, we show that the Poisson-Mellin-Newton cycle can be used on the exponential generating function to obtain a closed formula to compute the probability for a set to be a minimal transversal, that did not appear in [11]. Section 6 contains our perspectives and how we intend to improve our results using an even more general random model. Section 7 contains the full detailed proofs.

## 2 Random models

The two following random models we present in this section already appear in [11]. The hypergraph $\mathcal{H}$ can be seen as a binary matrix $M(\mathcal{H}) = (\chi_{i,j}(\mathcal{H}))_{i=1..m,j=1..n}$, called the incidence matrix of $\mathcal{H}$, with $\chi_{i,j}(\mathcal{H}) = 1$ if and only if the vertex $v_j$ belongs to the hyperedge $e_i$. In the first random model, the columns and the rows of the matrix are independent. It can be seen as the adaptation of the Erdös-Renyi model [18] on hypergraphs.

**Definition 1** ($\mathcal{HG}(m, n, p)$ random model). Let $p \in [0, 1]$ be a parameter. In the $\mathcal{HG}(m, n, p)$ model, the family of random variables $(\chi_{i,j}(\mathcal{H}))_{i=1..m,j=1..n}$ forms an independent family of random variables where for all $(i, j)$, $\chi_{i,j}$ follows a Bernoulli law of parameter $p$.

The second model generalizes the previous one.

**Definition 2** ($\mathcal{HG}(m, n, \pi)$ random model). Fix a sequence $\pi = (\pi_1, \dots, \pi_n)$ in $[0, 1]^n$ of real parameters. In the $\mathcal{HG}(m, n, \pi)$ model, the family of random variables $(\chi_{i,j}(\mathcal{H}))_{i=1..m,j=1..n}$ forms an independent family of random variables where for all $(i, j)$, $\chi_{i,j}$ follows a Bernoulli law of parameter $p_j$.

All the rows (hyperedges) follow the same distribution conversely to the columns where the degree of the vertex $v_j$ follows a binomial law of parameter $(m, p_j)$. Then, the average degree of $v_j$ is controlled and is $mp_j$.

In [11], the authors obtain precise bounds on the average number of transversals and minimal transversals in the $\mathcal{HG}(m, n, p)$ model, and some less precise results in the $\mathcal{HG}(m, n, \pi)$ model. In this paper, we obtain more precise results than in [11] in the $\mathcal{HG}(m, n, p)$ model and some versions of the $\mathcal{HG}(m, n, \pi)$ model.

## 3 Berge Algorithm and parameters of interest

Given two simple hypergraphs $\mathcal{H} = (\mathcal{V}, \mathcal{E})$ and $\mathcal{H}' = (\mathcal{V}', \mathcal{E}')$ where $\mathcal{E} = \{e_1, \dots, e_m\}$ and $\mathcal{E}' = \{e'_1, \dots, e'_{m'}\}$. There are two different “unions”, namely $\mathcal{H} \cup \mathcal{H}'$ and $\mathcal{H} \vee \mathcal{H}'$ which are defined as follows.

$$ \mathcal{H} \cup \mathcal{H}' = \{e_1, e_2, \dots, e_m, e'_1, e'_2, \dots, e'_{m'}\} $$

$$ \mathcal{H} \vee \mathcal{H}' = \{e_i \cup e'_j; i = 1, 2, \dots, m, \quad j = 1, 2, \dots, m'\} $$

**Proposition 1.** [5] Let $\mathcal{H}$ and $\mathcal{H}'$ be two simple hypergraphs. Then

$$ \mathrm{Tr}(\mathcal{H} \cup \mathcal{H}') = \min(\mathrm{Tr}(\mathcal{H}) \vee \mathrm{Tr}(\mathcal{H}')) $$
XX:4 On the average complexity of Berge Algorithm

The Berge algorithm, as described in [5], uses Proposition 1 to generate the transversal hypergraph through the following procedure. Given a hypergraph $\mathcal{H}$ with edges $\mathcal{E} = \{e_1, e_2, \dots, e_m\}$, let $H_i = \{e_1, e_2, \dots, e_i\}$ for $i = 1, 2, \dots, m$. The transversal hypergraph of $H_i$ is determined as

$$ \mathrm{Tr}(H_i) = \min[\mathrm{Tr}(\mathcal{H}_{i-1}) \lor \mathrm{Tr}(\{e_i\})] = \min[\mathrm{Tr}(\mathcal{H}_{i-1}) \lor \{v | v \in e_i\}]. $$

This result is an iterative computation process, known as Berge algorithm, eventually yielding $\mathrm{Tr}(\mathcal{H}) = \mathrm{Tr}(\mathcal{H}_m)$. The given pseudocode for the Berge algorithm is as follows.

Algorithm 1 Berge Algorithm

1 Initialize $\mathrm{Tr}(\mathcal{H}_1)$ with the vertices $v$ for $v \in e_1$;

2 for $i = 2$ to $m$ do

3 $\quad \mathrm{Tr}(\mathcal{H}_i) = \min[\mathrm{Tr}(\mathcal{H}_{i-1}) \lor \{v | v \in e_i\}]$;

4 Output $\mathrm{Tr}(H_m)$;

The order in which hyperedges are considered has an impact on the algorithm's efficiency. A natural question is therefore to establish an optimal order for the hyperedges and check whether it has an impact on the worst-case complexity. This question has been addressed by Takata [40], who demonstrated that the Berge algorithm is at least super-polynomial for any order. He gives a characterization of hypergraphs for which this lower bound is reached:

136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000

► Theorem 1. [40] The running time of the Berge algorithm on the family of hypergraphs $\mathcal{G}_i(i \in \mathbb{N})$ is superpolynomial in the size of the input and output no matter how the hyperedges are ordered.

Let's now consider the complexity of Berge algorithm. For each minimal transversal $M \in \mathrm{Tr}(\mathcal{H}_{i-1})$, the algorithm adds a vertex $v \in e_i$ and check minimality, which can be done in time $\Theta(|M| \times i)$ and space $\Theta(|M|)$, using an hash table. Since $|M| \le \min\{n, i\}$, the cost of Berge algorithm over a hypergraph $\mathcal{H} = (\mathcal{V}, \mathcal{E})$, noted $B(\mathcal{H})$, is in the following range:

$$ \sum_{i=2}^{m} |\mathrm{Tr}(\mathcal{H}_{i-1})| \cdot |e_i| \le B(\mathcal{H}) \le \sum_{i=2}^{m} |\mathrm{Tr}(\mathcal{H}_{i-1})| \cdot |e_i| \cdot \min\{n, i\} \cdot i $$

In the $\mathcal{H}\mathcal{G}(m, n, \pi)$ model, let $\mathbb{E}_{\pi}[\mathrm{Tr}_{m,n}]$ be the average number of minimal transversal in a hypergraph with $m$ hyperedges and $n$ vertices and $\mathbb{E}_{\pi}[B(\mathcal{H})]$ the average complexity of Berge algorithm. We have:

$$ \sum_{i=1}^{m-1} \mathbb{E}_{\pi}[\mathrm{Tr}_{i,n}] \le \mathbb{E}_{\pi}[B(\mathcal{H})] \le n \cdot m \cdot \min\{n, m\} \sum_{i=1}^{m-1} \mathbb{E}_{\pi}[\mathrm{Tr}_{i,n}] $$

Let $c_{m,X}$ be the probability for a set $X$ of size $\ell$ to be a minimal transversal in a hypergraph with $m$ hyperedges. We have:

$$ \mathbb{E}_{\pi}[\mathrm{Tr}_{m,n}] = \sum_{\ell=1}^{\min\{n,m\}} \sum_{\substack{X \subseteq \{1, \dots, n\} \\ |X| = \ell}} c_{m,X} $$
In the $\mathcal{HG}(m, n, p)$ model, the formula simplifies. Let $\mathbb{E}_p[\mathrm{Tr}_{m,n}]$ be the average number of minimal transversal and $c_{m,\ell}$ be the probability for a set of size $\ell$ to be a minimal transversal. We have:

$$ \mathbb{E}_p[\mathrm{Tr}_{m,n}] = \sum_{\ell=1}^{\min\{n,m\}} \binom{n}{\ell} c_{m,\ell} $$

Regarding the average complexity of Berge algorithm we have:

$$ \sum_{i=1}^{m-1} \mathbb{E}_p[\mathrm{Tr}_{i,n}] = \sum_{i=1}^{m-1} \sum_{\ell=1}^{\min\{n,m\}} \binom{n}{\ell} c_{i,\ell} = \sum_{\ell=1}^{\min\{n,m\}} \binom{n}{\ell} \sum_{i=1}^{m-1} c_{i,\ell}. \quad (1) $$

We call cumulative sum, noted $\bar{c}_{m,\ell}$, the value $\sum_{i=1}^{m-1} c_{i,\ell}$. We have $\sum_{i=1}^{m-1} \mathbb{E}_\pi[\mathrm{Tr}_{i,n}] = \sum_{\ell=1}^{\min\{n,m\}} \binom{n}{\ell} \bar{c}_{m,\ell}$. In Section 4, we give an exponential and an ordinary probabilistic generating function whose coefficient is $c_{m,X}$ and an o.p.g.f whose coefficient is $\bar{c}_{m,\ell}$.

# 4 Generating functions

## 4.1 Exponential generating function

Given a probability distribution $\pi = (\pi_1, \dots, \pi_n)$, let's consider $\ell$ columns of the incidence matrix $M(H)$. Let $X = \{x_1, \dots, x_\ell\} \subseteq \{1, \dots, n\}$ be the set of selected columns. We have $(p_1, \dots, p_\ell) = (\pi_{x_1}, \dots, \pi_{x_\ell})$ the restriction of $\pi$ over the $\ell$ columns. The probability that a row contains only zeros over those $\ell$ columns is given by $z_\ell(\pi) = (1-p_1)(1-p_2)\cdots(1-p_\ell)$. From now on, if there is no ambiguity, we will use $z_\ell$ instead of $z_\ell(\pi)$. The probability that a row contains exactly one 1 (at column $i$) over the $\ell$ columns is given by $o_{\ell,i} = \frac{p_i}{1-p_i}z_\ell$. Finally the probability that a row contains at least two 1 is $1 - z_\ell - \sum_{i=1}^\ell o_{\ell,i}$.

**Proposition 2.** In the $\mathcal{HG}(m, n, \pi)$ model, the probabilistic generating function of a set $C$ of $\ell$ vertices to be a minimal transversal is

$$ S_{\ell}(u) = e^{(1-z_{\ell}) \cdot u} \prod_{i=1}^{\ell} (1 - e^{-o_{\ell,i} \cdot u}) $$

**Proof.** The proof in the $\mathcal{HG}(m, n, \mu)$ model consist in an integration over $\mathcal{HG}(m, n, \pi)$ models. Assume that we have a distribution $\pi = (p_1, \dots, p_n)$. In the p.g.f. $S_\ell(u)$, the variable $u$ marks each line of the matrix $(\chi_{i,j}(H))_{i=1..m,j=1..n}$. For fixed $n$ and $\ell$, the probability that a set of size $\ell$ of vertices is a minimal transversal of a random hypergraph with $m$ hyperedges is given by $m![u^m]S_\ell(u)$. First let's note that everything that happens on the $n-\ell$ columns that are not related to our set of vertices is irrelevant to determine if the set is a minimal transversal. Therefore we can restrict our distribution $\pi$ to $(p_1, \dots, p_\ell)$ (up to a relabeling of the $p_i$). The formula can then be obtained by using the symbolic method [19]. The p.g.f. of a non-empty set of lines that contain exactly one 1 at position $i$ is $e^{o_{\ell,i} \cdot u} - 1$. Such lines exists for each position between 1 and $\ell$. Every remaining lines has to contain at least two 1. The associated p.g.f. is given by $e^{(1-z_\ell - \sum_{i=1}^\ell o_{\ell,i}) \cdot u}$. Combining all those parameters we obtain the generating function:

$$ \left[ \prod_{i=1}^{\ell} (e^{o_{\ell,i} \cdot u} - 1) \right] e^{(1-z_{\ell} - \sum_{i=1}^{\ell} o_{\ell,i}) \cdot u} $$

after a step of simplification where $e^{(-\sum_{i=1}^\ell o_{\ell,i} \cdot u)}$ is added in the product, we obtain the announced results.

<figure><img src="image_3.png" /></figure>
XX:6 On the average complexity of Berge Algorithm

174 4.2 Ordinary generating function

The Borel transform of an exponential generating function $S_\ell(u)$ allows to obtain an ordinary generating function $\hat{S}_\ell(u)$ sharing the same coefficients. It is defined as follows.

$$
\hat{S}_{\ell}(u) = \int_{0}^{\infty} S_{\ell}(tu)e^{-t}dt
$$

Applying the Borel transform to our exponential generating function ultimately yields the
following ordinary generating function:

$$
\hat{S}_{\ell}(u) = u^{\ell}\ell! \frac{1}{1-u(1-z_{\ell})} \prod_{i=1}^{\ell} \frac{o_{\ell,i}}{1-u(1-z_{\ell}-io_{\ell,i})}
$$

This generating function actually has a nice combinatorial interpretation: recall that the variable $u$ mark each line. The $u^\ell \prod_{j=1}^\ell o_{\ell,j}$ therefore denotes $\ell$ lines that contains exactly one 1, one for each $\ell$ columns. The $\ell!$ allows to choose the order in which they appear. We'll call those lines separators. They guarantee the "minimality" property. After the $\ell$-i-th separator has been added in the matrix and until the next separator is added, each row cannot contain only zeros and cannot contain only one 1 in one of the $i$ remaining positions. This probability is given by $(1-z_\ell - io_\ell)$. A sequence of such rows is given by the quasi inverse $\frac{1}{1-u(1-z_\ell - io_\ell)}$. The product is obtained to deal with each block between each separators. Note that in the $\mathcal{HG}(m, n, p)$ model, the function simplifies into $\hat{S}_\ell(u) = u^\ell \ell! o_\ell^\ell \prod_{i=0}^\ell \frac{1}{1-u(1-z_\ell - io_\ell)}$. Given the formal expression for $\hat{S}_\ell(u)$, we have:

$$
\hat{S}_{\ell}(u) = \sum_{m \ge 0} c_{m, \ell} u^m
$$

The generating function for the sequence {$\bar{c}_{i,\ell}$}$_1^\infty$ is denoted by $\bar{S}_\ell(u)$, which can be written as $\bar{S}_\ell(u) = \sum_{m \ge 0} \bar{c}_{m,\ell} u^m$. This function, $\bar{S}_\ell(u)$, is referred to as the cumulative generating function:

$$
\bar{S}_{\ell}(u) = \frac{1}{1-u} \hat{S}_{\ell}(u)
$$

We will use the coefficients of $\bar{S}_\ell(u)$ in calculating the average-case complexity of the Berge algorithm.

175

176

177

5 Main results

178

179

180

Figure 1 summarizes our contributions and the main results of this paper. In the $\mathcal{HG}(m, n, \pi)$ model, we recall that $z_\ell = \prod_{i=1}^\ell (1-p_i)$, where $(p_1, \dots, p_\ell)$ is the restriction of $\pi$ over the vertices of a set $X$ of cardinal $\ell$.

181

182

► **Theorem 2.** In the $\mathcal{HG}(m, n, \pi)$ model, the probability for a set $X$ of cardinal $\ell$ to be a minimal transversal, or $c_{m,X}$ is as follows:

183

$$
c_{m,X} = \begin{cases}
(1-z_\ell)^m \left(1 + \mathcal{O}\left(\frac{\log m}{m^{1-\epsilon}}\right)\right) & \text{for } mz_\ell \ge m^\epsilon, \\
\binom{m}{\ell} \ell! \left(\prod_{i=1}^\ell o_{\ell,i}\right) \left(1 + \mathcal{O}\left(\frac{\log m}{m^{1-\epsilon}}\right)\right) & \text{for } mz_\ell \le m^{-\epsilon}, \\
\frac{m^m}{e^m} \frac{S_\ell(r)}{r^m} \left(1 + \mathcal{O}\left(m^{-1/3} + \frac{l}{m}\right)\right) & \text{for } m^{-\epsilon} \le mz_\ell \le m^\epsilon
\end{cases}
$$

184

185

The results from Theorem 2 are based on the value of $mz_{\ell}$. For $mz_{\ell} \ge m^{\epsilon}$ and $mz_{\ell} \le m^{-\epsilon}$,
the results are the asymptotics of the coefficients of the ordinary generating function, and
<figure><img src="image_4.png" /><figcaption>Figure 1 Summary of our main results and methods.</figcaption></figure>

obtained by Cauchy's formula (Lemmas 13 and 14). It should be noted that for simplicity, we have proved Lemmas 13 and 14 for $\mathcal{H}\mathcal{G}(m, n, p)$ model. The same argument works for $\mathcal{H}\mathcal{G}(m, n, \pi)$ model and gives the desired results. For $m^{-\epsilon} \le m z_{\ell} \le m^{\epsilon}$, the result is derived from the asymptotics of the coefficients of the exponential generating function using the saddle point method, in which $r$ is the saddle point (Lemma 7).

Restricting our focus to the $\mathcal{H}\mathcal{G}(m, n, p)$ model and defining $q = 1 - p$, the following corollary is a consequence of Theorem 2.

**Corollary 3.** In the $\mathcal{H}\mathcal{G}(m, n, p)$ model, the probability of $\ell$ given vertices to be a minimal transversal, is as follows:

$$c_{m,\ell} = \begin{cases} (1-z_{\ell})^m \left(1+O\left(\frac{\log m}{m^{1-\epsilon}}\right)\right) & \text{for } \ell \le \log_{\frac{1}{q}} m^{1-\epsilon}, \\ \binom{m}{\ell} o_{\ell}^{\ell} \ell! \left(1+O\left(\frac{\log m}{m^{1-\epsilon}}\right)\right) & \text{for } \ell \ge \log_{\frac{1}{q}} m^{1+\epsilon}, \\ e^{-m z_{\ell}} (1-e^{-o_{\ell}r})^{\ell} \left(1+O\left(\frac{1}{m^{1-2\epsilon}}\right)\right) & \text{for } \log_{\frac{1}{q}} m^{1-\epsilon} \le \ell \le \log_{\frac{1}{q}} m^{1+\epsilon} \end{cases}$$

Regarding the cumulative sum, we obtained results using the ordinary generating function.

**Proposition 3.** In the $\mathcal{H}\mathcal{G}(m, n, p)$ model, we have

$$\bar{c}_{m,\ell} = \begin{cases} \Gamma(\frac{q}{p}) \frac{\ell!}{\Gamma(\frac{q}{p} + \ell + 1)} \frac{1}{o_{\ell}} \left(1 + O\left(\frac{\log m}{m^{\epsilon}}\right)\right) & \text{for } \ell \le \log_{\frac{1}{q}} m^{1-\epsilon}, \\ \binom{m+1}{\ell+1} o_{\ell}^{\ell} \ell! \left(1 + O\left(\frac{\log m}{m^{1-\epsilon}}\right)\right) & \text{for } \ell \ge \log_{\frac{1}{q}} m^{1+\epsilon} \end{cases}$$

and for $\log_{\frac{1}{q}} m^{1-\epsilon} \le \ell \le \log_{\frac{1}{q}} m^{1+\epsilon}$

$$\ell! o_{\ell}^{\ell} \binom{j_0}{\ell} (1 - z_{\ell} - \ell o_{\ell})^{j_0 - \ell} \le \bar{c}_{m,\ell} \le (m - \ell) \ell! o_{\ell}^{\ell} \binom{j_1}{\ell} (1 - z_{\ell})^{j_1 - \ell}$$

$$\text{with } j_0 = \min \left( m, \left\lfloor \frac{\ell}{z_{\ell} + \ell o_{\ell}} \right\rfloor \right), \quad j_1 = \min \left( m, \left\lfloor \frac{\ell}{z_{\ell}} \right\rfloor \right).$$
XX:8 On the average complexity of Berge Algorithm

202 The method to obtain the first two asymptotics is similar to the one used to extract $c_{m,l}$ and is described in Lemmas 13 and 14. The proof of the last inequalities, given in Lemma 15 is a direct consequence of intermediates bounds used in the proof of Lemmas 13.

204 Let $av(n, m, \ell)$ be the average number of minimal transversals of size $\ell$ in the $\mathcal{H}\mathcal{G}(m, n, p)$ model. The average number of minimal transversal is equal to

$$ \sum_{\ell=1}^{\min\{m,n\}} av(n,m,\ell) = \sum_{\ell=1}^{\min\{m,n\}} \binom{n}{\ell} m![u^m]S_{\ell}(u) = \sum_{\ell=1}^{\min\{m,n\}} \binom{n}{\ell} c_{m,\ell} $$

205 We obtain the asymptotics when $m$ is greater than $n$.

► **Proposition 4.** In the $\mathcal{H}\mathcal{G}(m, n, p)$ model, assume that there exists a constant $0 < \alpha < 1$ such that $n = m^{\alpha}$. The average number of minimal transversals in the $\mathcal{H}\mathcal{G}(m, n, p)$ model is asymptotically equivalent to

$$ av(n, m, \lfloor j \rfloor) + av(n, m, \lfloor j + 1 \rfloor) + av(n, m, \lfloor j + 2 \rfloor) $$

206 with $j = \log_{\frac{1}{p}}(\frac{mp}{\kappa}) + 1$ where $\kappa$ is the unique solution to $\alpha + \log_{\frac{1}{p}}(\frac{1-e^{-(1-p)\kappa}}{1-e^{-\kappa}}) = 0$

207 Note that the asymptotic is concentrated around only three positions. First we prove that $av(n, m, \lfloor j + 1 \rfloor)$ is maximal by studying the ratio of two consecutive elements. This ratio is decreasing and is close to 1 for $\ell$ around $j$. It also tends to 0 for $\ell > j + 1$ or to $+\infty$ for $\ell < j - 1$ which implies that the other elements are negligible. These last two points use the fact that $n = m^{\alpha}$ with $\alpha < 1$. For $\alpha > 1$, the asymptotic is smoother but it is out of scope of this article. Also, in practice (the *Frequent Itemset Mining Dataset Repository* for instance), the assumption that $\alpha$ is smaller than 1, that is $m > n$, seems reasonable. The detailed proof is given in Section 7.3.

208 The complexity of Berge algorithm is lower and upper bounded, up to a polynomial term, by the double sum given in Equation (1) which involves the cumulative sums $\bar{c}_{m,\ell}$. Basing ourselves on Proposition 3, we consider the following decomposition:

$$ \sum_{i=1}^{m-1} \mathbb{E}_{\pi}[\mathrm{Tr}_{i,n}] = \sum_{\ell=1}^{\log_{\frac{1}{q}} m^{1-\epsilon}} \binom{n}{\ell} \bar{c}_{m,\ell} + \sum_{\ell=\log_{\frac{1}{q}} m^{1-\epsilon}}^{\log_{\frac{1}{q}} m^{1+\epsilon}} \binom{n}{\ell} \bar{c}_{m,\ell} + \sum_{\ell=\log_{\frac{1}{q}} m^{1+\epsilon}}^{\min\{n,m\}} \binom{n}{\ell} \bar{c}_{m,\ell} $$

215 By proving the first and the third sum are equivalent to the first and the last term of the second sum, we conclude that the second sum is the one that matter asymptotically. Then, by identifying the $\ell$ that maximizes the coefficient $\bar{c}_{m,\ell}$, we deduce an upper bound on the average complexity of the Berge algorithm.

216 ► **Proposition 5.** In the $\mathcal{H}\mathcal{G}(m, n, p)$ model, assume that there exists a constant $1 - \frac{p}{\ln(\frac{1}{1-p})} < \alpha < 1$ such that $n = m^{\alpha}$. For all $\epsilon > 0$, the average complexity of the Berge algorithm satisfies

$$ \mathbb{E}_p[B(\mathcal{H})] \le \epsilon n^2 m^2 (\log_{\frac{1}{q}} m) \ell! o_{\ell} \binom{n}{\ell} \binom{m}{\ell} (1 - z_{\ell})^{m-\ell} (1 + o(1)) $$

219 with $\ell = \log_{\frac{1}{q}}(m) - \log_{\frac{1}{q}}(\ln m) - \log_{\frac{1}{q}}(\frac{1-\alpha}{p}) + o(1)$.

220 The complete proof is given in Section 7.4. The condition on $\alpha$ is mainly technical and other results can be obtained if $1 - \frac{p}{\ln(\frac{1}{1-p})} \ge \alpha$.

221 To evaluate the result of Proposition 5 in $\ell = \log_{\frac{1}{q}}(m) - \log_{\frac{1}{q}}(\ln m) - \log_{\frac{1}{q}}(\frac{1-\alpha}{p}) + o(1)$ helps clarifying the asymptotics.
► **Theorem 4.** In the $\mathcal{HG}(m, n, p)$ model, assume that there exists a constant $1 - \frac{p}{\ln(\frac{1}{p-1})} < \alpha < 1$ such that $n = m^\alpha$. The average complexity of the Berge algorithm is

$$ \mathbb{E}_p[B(\mathcal{H})] = \mathcal{O}\left(n^{\ell+2} m^4 \log_{\frac{1}{q}}(m) (1-\alpha)^{\ell} \frac{1}{m^{\frac{1-\alpha}{p}}}\right) $$
with $\ell = \log_{\frac{1}{q}}(m) - \log_{\frac{1}{q}}(\ln m) - \log_{\frac{1}{q}}(\frac{1-\alpha}{p}) + o(1)$. 226

Note that a more precise upper bound could be obtained: we upper bounded a ratio $\frac{\ln(m)^{\ell-1}}{l!}$ by $m$ in the formula to make it easier to read. Indeed, we can now clearly see that the dominant term is a quasi-polynomial in $n$. It can be proven using Proposition 4 that the number of solutions computed by the Berge algorithm is also quasi-polynomial. Therefore we can conclude with the following corollary.

► **Corollary 5.** In the $\mathcal{HG}(m, n, p)$ model, assume that there exists a constant $1 - \frac{p}{\ln(\frac{1}{p-1})} < \alpha < 1$ such that $n = m^\alpha$. The average output complexity of the Berge algorithm is quasi-linear.

## 5.1 Another Point of view

In this section, we show how the Poisson-Mellin-Newton cycle can be used as a transformation between the analytic combinatorics point of view and the probabilistic point of view.

Restricting ourselves $\mathcal{HG}(m, n, p)$ model, we recall that the probabilistic generating function that a given set of $\ell$ vertices is a minimal transversal is:

$$ S_{\ell}(u) = e^{(1-(1-p)^{\ell})u} \left(1 - e^{-p(1-p)^{\ell-1}u}\right)^{\ell} $$

The Poisson generating function is $P_l(u) = e^{-u}S_l(u)$.

It can be shown that, after applying a Mellin transform, we obtain:

$$ M_l(s) = \sum_{k=0}^{l} (-1)^{l-k} \binom{l}{k} \frac{\Gamma(s)}{(1-p)^{(l-1)s}(1-p+lp-kp)^s} $$

The coefficient of the original function are now given by the Rice integral:

$$ c_{m,l} = \frac{1}{2\pi i} \int_{\Lambda} \frac{\Gamma(m+1)}{\Gamma(m+s+1)} M_l(s) ds $$

After several steps of simplification we obtain:

$$ c_{m,l} = \sum_{i=\ell}^{m} \binom{m}{i} l! \binom{i}{l} (1 - (1-p)^l - l \cdot p(1-p)^{l-1})^{m-i} \cdot (p(1-p)^{l-1})^i $$

This formula has a combinatorial interpretation: given a set of size $\ell$, its probability to be a minimal transversal of a random hypergraph with $m$ hyperedges is given by:

- there is at least $\ell$ lines that contains only one 1, that is at least one per vertex. Assume there are $i$ such lines. Then there is $\binom{m}{i}$ possibilities to select such lines.

- then, the $i$ lines have to be distributed amongst the $\ell$ vertices, that is a set composition of $\{1, \dots, i\}$ into $\ell$ subsets. There are $l!\binom{i}{l}$ ways to do so, where $\binom{i}{l}$ are the Stirling number of the second kind.

- The probability that each of the $i$ lines contains exactly one 1 is given by $(p(1-p)^{l-1})^i$.

- The probability that the rest of the $m-i$ lines contain at least two 1 is given by $(1 - (1-p)^l - l \cdot p(1-p)^{l-1})^{m-i}$.

Note that such closed formula did not appear in [11].
XX:10 On the average complexity of Berge Algorithm

6 Perspectives

256

In the future, we would like to consider a third model that we consider powerful enough to
capture the complexity of real datasets but is in a sense simpler since all the columns have
the same probabilistic behaviour.

257

258

259

260

► **Definition 3** ($\mathcal{HG}(m, n, \mu)$ random model). Fix $\mu$ a probability measure over $[0, 1]$. In the $\mathcal{HG}(m, n, \mu)$ model, the incidence matrix $M(\mathcal{H})$ is generated according to the following procedure:

261

262

1. Compute a random vector $\pi = (\pi_1, \dots, \pi_n)$ where $(\pi_1, \dots, \pi_n)$ forms a family of i.i.d random variables with probability measure $\mu$;

263

264

2. Compute $M(\mathcal{H})$ according to the multiparametric model $\mathcal{HG}(m, n, \pi)$.

265

266

With the $\mathcal{HG}(m, n, \mu)$ random model, the distribution of the degrees is controlled and it
is possible to describe the influence of the degrees on the number of minimal transversals.
The columns of the matrix remain independent but the rows are no more independent since
they share the same random variable $\pi$. Models are closely related:

267

268

269

270

$$
\mathbf{Pr}_{m,n,\mu}[\mathbf{H}] = \int_{[0,1]^n} \mathbf{Pr}_{m,n,\pi}[\mathbf{H}]d\mu_{\otimes n}(\pi) \quad (2)
$$

271

with $\mu_{\otimes n}$ the product measure $\mu \otimes \dots \otimes \mu$ ($n$ times). Also, if we consider the Dirac Measure
$\mu = \delta_p$, then $\mathcal{HG}(m, n, \delta_p)$ is exactly the $\mathcal{HG}(m, n, p)$ model. To the best of our knowledge,
this idea is new in the field of algorithm analysis and so is our approach to obtain results
in this random model. It is general enough to capture the behaviour of algorithm in both
classical models like the Erdös-Renyi and on real-world hypergraphs. Though we only gave
the average complexity of Berge algorithm in the $\mathcal{HG}(m, n, p)$ model, the results we presented
already allow to numerically compute the average cost of the algorithm in both $\mathcal{HG}(m, n, \pi)$
and $\mathcal{HG}(m, n, \mu)$ models. In our perspectives, we would like to obtain the average number of
minimal transversals and complexity of Berge algorithm for other measures $\mu$ like

272

273

274

275

276

277

278

279

280

■ the uniform distribution between two values a and b, that is $\mu = \mathcal{U}[a, b]$;

281

■ a measure that combines two Dirac measures;

282

■ the Dirac measure (or one of the two previously mentioned), when the probability $p$ is
close to 0 and/or when $n$ is not polynomial in $m$.

283

284

Note that, in the $\mathcal{HG}(m, n, p)$ model, we claim to be able to extract the average number of minimal transversals with $n$ vertices and $m$ hyperedges when $m < n$, that is $n = m^\alpha$ with $\alpha > 1$. We omitted the proof for the clarity of the paper and since we are convinced that, in practice, it is safe to assume that $\alpha < 1$. The case where $n$ is almost equal to $m$ remains a challenge though. Our results could also be applied to study algorithms which are improvements of Berge Algorithm, as mentioned in the introduction. Finally, in order to fully understand why Berge algorithm is more efficient in practice than the one by Fredman and Khachiyan [20], one would also require to analyse this algorithm in various random models.

285

286

287

288

289

290

291
7 Details of the proofs

292

7.1 Details for the EGF

293

In the H G(m, n, π) model, for a given distribution π, the e.g. f is

$$
S_{\ell}(u) = e^{(1-z_{\ell}) \cdot u} \prod_{i=1}^{\ell} (1 - e^{-o_{\ell,i} \cdot u})
$$

294

it can be rewritten as:

$$
S_{\ell}(u) = e^{((1-z_{\ell})u - \sum_{i=1}^{\ell} o_{\ell,i} u)} \prod_{i=1}^{\ell} (e^{o_{\ell,i} u} - 1) = e^{(1-z_{\ell} - \sum_{i=1}^{\ell} o_{\ell,i}) u} \prod_{i=1}^{\ell} (e^{o_{\ell,i} u} - 1)
$$

295

Our goal is to find $m![u^m]S_\ell(u)$, that is the probability of a set with $\ell$ vertices to be a minimal transversal in a hypergraph with $m$ hyperedges. The idea of the proof is the following: $S_\ell(u)$ is analytic, we can therefore use the saddle-point method to extract its coefficient, using a circle of radius $r$ as a closed path. Indeed, using Cauchy's integral formula we have

$$
[u^m] S_\ell(u) = \frac{1}{2\pi i} \int_{|u|=r} \frac{S_\ell(u)}{u^{m+1}} du
$$

296

where $r$ is between 0 and the radius of convergence. Let $h(\theta) = \ln(S_\ell(re^{i\theta}))$, we have

$$
[u^m] S_\ell(u) = \frac{1}{2\pi r^m} \int_{-\pi}^{\pi} e^{h(\theta) - im\theta} d\theta
$$

297

298

Using the Taylor expansion we obtain

$$
[u^m] S_{\ell}(u) = \frac{1}{2\pi r^m} \int_{-\pi}^{\pi} e^{h(0) + \theta h'(0) + \frac{\theta^2}{2} h''(0) + \mathcal{O}(\theta^3 \sup_{\theta \in [-\pi, \pi]} |h'''(\theta)|) - im\theta} d\theta
$$

299

Therefore, we need to find the first, second, and third derivative of $h(\theta)$.

300

$h'(\theta)$ can be computed as follows:

301

$$
h'(\theta) = i re^{i\theta} \frac{S'_{\ell}(re^{i\theta})}{S_{\ell}(re^{i\theta})} = ia(re^{i\theta}), \quad \text{where} \quad a(x) = x \frac{S'_{\ell}(x)}{S_{\ell}(x)}
$$

302

303

$$
a(x) = x \left[ (1 - z_{\ell}) + \sum_{i=1}^{\ell} \frac{o_{\ell,i} e^{-o_{\ell,i} x}}{1 - e^{-o_{\ell,i}}} \right] = x(1 - z_{\ell}) + \sum_{i=1}^{\ell} \omega(o_{\ell,i} x)
$$

304

305

$$
\text{with} \quad \omega(x) = \frac{xe^{-x}}{1 - e^{-x}} = \frac{x}{e^x - 1}
$$

306

Now, $h''(\theta)$ can be computed as:

307

$$
h''(\theta) = -re^{i\theta}a'(re^{i\theta}) := -b(re^{i\theta}), \quad \text{with} \quad b(x) = xa'(x)
$$

308

$$
\Rightarrow b(x) = x \left[ (1 - z_{\ell}) + \sum_{i=1}^{\ell} o_{\ell,i} \omega'(o_{\ell,i} x) \right]
$$

309

310

$$
= (1 - z_{\ell})x + \sum_{i=1}^{\ell} o_{\ell,i} x \omega'(o_{\ell,i} x)
$$

311
XX:12 On the average complexity of Berge Algorithm

312 Where,

$$
313 \quad \omega'(x) = \frac{1}{e^x - 1} - x \frac{e^x}{(e^x - 1)^2} = \frac{e^x - 1 - xe^x}{(e^x - 1)^2}
$$

314 And $h'''(\theta)$ is obtained as:

$$
315 \quad h'''(\theta) = -ire^{i\theta}b'(re^{i\theta}) = -ic(re^{i\theta})
$$

316 with $c(x) = xb'(x)$

$$
317 \quad = x \left[ (1 - z_l) + \sum_{i=1}^{l} o_{l,i} \omega'(o_{l,i} x) + \sum_{i=1}^{l} o_{l,i}^2 x \omega''(o_{l,i} x) \right]
$$

$$
318 \quad \begin{aligned}
&= x(1 - z_l) + \sum_{i=1}^{\ell} o_{\ell,i} x \omega'(o_{\ell,i} x) + \sum_{i=1}^{\ell} (o_{\ell,i} x)^2 \omega''(o_{\ell,i} x) \\
&\qquad - b(x) + \sum_{i=1}^{\ell} (o_{\ell,i} x)^2 \omega''(o_{\ell,i} x)
\end{aligned}
$$

$$
320 \quad \begin{aligned}
&= b(x) + \sum_{i=1}^{\ell} (o_{\ell,i}x)^2 \omega''(o_{\ell,i}x) \\
&\text{We have}
\end{aligned}
$$

322 We have

$$
323 \quad [u^m] S_\ell(u) = \frac{S_\ell(r)}{2\pi r^m} \int_{-\pi}^{\pi} e^{i\theta(a(r)-m) - \frac{\theta^2}{2}b(re^{i\theta}) + \mathcal{O}(\theta^3 \sup_{\theta \in [-\pi, \pi]} |h'''(\theta)|)} d\theta
$$

324 We define the notion of H-admissibility as it was in [19].

325 ▶ **Definition 6 (H-admissible).** Let $G(z)$ be a generating function with a radius of convergence $R$ with $0 < R \le \infty$. Given $R_0 < R$, let $G(z)$ be positive for $z \in ]R_0, R[$. $G(z)$ is said to be H-admissible if it satisfies the following conditions:

328 1. (Capture condition) $\lim_{r \to R} a(r) = +\infty$ and $\lim_{r \to R} b(r) = +\infty$

329 2. (Locality condition) for some function $\theta_0(r)$ defined over $]R_0, R[$, and satisfying $0 < \theta_0 < \pi$, one has

$$
329 \quad \begin{gathered}
G(re^{i\theta}) \sim G(r)e^{i\theta a(r) - \theta^2 b(r)/2} \quad \text{as} \quad r \mapsto R, \\
\text{uniformly in } |\theta| \le \theta_0(r)
\end{gathered}
$$

3. (Decay condition) Uniformly in $\theta_0(r) \le |\theta| < \pi$

$$
G(re^{i\theta}) = o\left(\frac{G(r)}{\sqrt{b(r)}}\right)
$$

330 ▶ **Lemma 7.** In the $\mathcal{H}G(m, n, \pi)$ model, when $\ell = o(m)$, the probability that a set with $\ell$
331 vertices is a minimal transversal is:

$$
332 \quad m![u^m] S_\ell(u) = m! \frac{S_\ell(r)}{\sqrt{2\pi b(r)r^m}} \left(1 + o\left(b(r)^{-\frac{2}{3}}\right)\right)
$$

333 **Proof.** The idea of the proof is to evaluate the integral

$$
334 \quad \int_{-\pi}^{\pi} e^{i\theta(a(r)-m) - \frac{\theta^2}{2}b(re^{i\theta}) + \mathcal{O}(\theta^3 \sup_{\theta \in [-\pi, \pi]} |h'''(\theta)|)} d\theta
$$

335 We decompose the integral into two, that is $[u^m]S_\ell(u) = I_1 + I_2$ with

$$
336 \quad I_1 = \int_{|\theta| \le \epsilon} e^{i\theta(a(r)-m) - \frac{\theta^2}{2}b(re^{i\theta}) + \mathcal{O}(\theta^3 \sup_{\theta \in [-\pi, \pi]} |h'''(\theta)|)} d\theta
$$

$$
337 \quad I_2 = \int_{\epsilon \le |\theta| \le \pi} e^{i\theta(a(r)-m) - \frac{\theta^2}{2}b(re^{i\theta}) + \mathcal{O}(\theta^3 \sup_{\theta \in [-\pi, \pi]} |h'''(\theta)|)} d\theta
$$

339 In order to use the saddle-point method and prove Lemma 7, we prove the following:
■ we show there exists a unique saddle point $r$ such that $a(r) = m$ (Lemma 8).

340

■ we show that $r \sim \frac{m-\ell}{1-z_\ell}$ (Lemma 9).

341

■ we show that $b(r)$ tends to infinity with respect to $r$ (Lemma 10).

342

■ in $I_1$, we show that if $\varepsilon = b(r)^{-\frac{4}{9}}$, we have $|\theta^3 h'''(\theta)| = m^{-\frac{1}{3}}$ (Lemma 11).

343

■ we give an upper bound of $I_2$ and show it is negligible compared to $I_1$ (Lemma 12).

344

Note that this is sufficient to prove that $S_\ell(u)$ is H-admissible. Once all those elements are
proven, we have that

$$
I_1 = (1 + O(m^{-\frac{1}{3}})) \int_{-\varepsilon}^{\varepsilon} e^{-\frac{\theta^2}{2} b(re^{i\theta})} d\theta
$$

Using $\varepsilon = b(r)^{-\frac{4}{9}}$, all that is left to study in $I_1$ is the Gaussian integral

$$
\int_{-b(r)^{-\frac{4}{3}}}^{b(r)^{-\frac{4}{3}}} e^{-\frac{\theta^2}{2} b(re^{i\theta})} d\theta
$$

Using a change of variable $s = \sqrt{b(r)}\theta$, and assuming $b(r)$ tends to infinity we obtain

$$
\int_{-\infty}^{\infty} e^{-\frac{s^2}{2}} \frac{ds}{\sqrt{b(r)}}
$$

which is equal to $\sqrt{\frac{2\pi}{b(r)}}$, therefore concluding the proof.

345

346

<figure><img src="image_5.png" /></figure>

In the context of Lemma 7, since the functions $\omega(x)$ and $x\omega'(x)$ are bounded on $[0, +\infty[$,
we have $r = \frac{m}{1-z_\ell} + \mathcal{O}(l)$ and $b(r) = m + (\mathcal{O}(l))$. By replacing $m!$ using the Stirling formula,
we obtain the result announced in Theorem 2 when $m^{-\epsilon} \le mz_\ell \le m^\epsilon$.

347

348

349

► **Lemma 8.** There exists a unique $r$ such that $a(r) = m$.

350

Proof. Recall that $a(x) = (1 - z_\ell)x + \sum_{i=1}^\ell \omega(o_{\ell,i}x)$. So,

351

$$
a'(x) = (1 - z_{\ell}) + \sum_{i=1}^{\ell} o_{\ell,i} \omega'(o_{\ell,i} x)
$$

352

and

353

$$
\omega'(x) = \frac{e^x}{(e^x - 1)^2} (1 - x - e^{-x}) \le 0
$$

354

so $\omega(x)$ is decreasing.

355

$$
\omega''(x) = \frac{e^{2x}}{(e^x - 1)^3} (x + xe^{-x} - 2 + 2e^{-x}) \geq 0
$$

356

Since $a''(x) \ge 0$, we have $a'(x)$ is increasing and $a'(0) = 1 - z_\ell + \sum_{i=1}^\ell o_{\ell,i}\omega'(0) = 1 - z_\ell - \frac{1}{2}\sum_{i=1}^\ell o_{\ell,i} > 0$. So $a'(x) > 0$ and $a(x)$ is increasing.

357

358

Moreover, $a(0) = \ell$ and $\lim_{x \to \infty} a(x) = \infty$ and we can conclude that $r$ exists uniquely.

359

<figure><img src="image_6.png" /></figure>

► **Lemma 9.** If $\ell = o(m)$, then $r \sim \frac{m}{1-z_\ell}$. Otherwise we have $r \sim \frac{m-\ell}{1-z_\ell}$.

360

Proof. Assuming $a(r) = m$, we have $r(1 - z_\ell) + \sum_{i=1}^\ell \omega(o_{\ell,i}r) = m$. Using the fact that $\omega(x) \in [0, 1]$, one has $\frac{m-\ell}{1-z_\ell} \le r \le \frac{m}{1-z_\ell}$.

361

362

For $k > 1$, if $\ell \ge k \log m$, then $\ell z_\ell m \to 0$

363

$$
r(1 - z_{\ell}) + \sum_{i=1}^{\ell} \omega(o_{\ell,i}r) = r(1 - z_{\ell}) + \sum_{i=1}^{\ell} (1 + \mathcal{O}(o_{\ell,i}r)) = r(1 - z_{\ell}) + \ell + \mathcal{O}(\ell z_{\ell} m)
$$

364
XX:14 On the average complexity of Berge Algorithm

thus, $m = r(1 - z_{\ell}) + \ell + O(\ell z_{\ell} m)$, so $r \sim \frac{m-\ell}{1-z_{\ell}}$.

If $\ell \le \log m$, then $r \sim \frac{m}{1-z_{\ell}} \sim \frac{m-\ell}{1-z_{\ell}}$.

367

◀

368 ▶ Lemma 10. If $\ell = o(m)$, then the function $b(r)$ tends to infinity.

369 ▶ Proof. We have

$$
370 \qquad b(r) = r(1 - z_{\ell}) + \sum_{i=1}^{\ell} o_{\ell,i} r \omega'(o_{\ell,i} r)
$$

371 Using the fact that $\omega'(o_{\ell,i}r) \le 0$, there exists a constant like $A \le 0$ such that $A \le o_{\ell,i}r\omega'(o_{\ell,i}r)$,

$$
372 \quad \forall i \le \ell. \text{ Therefore we obtain}
$$

$$
373 \qquad (1 - z_{\ell})r + \ell A \le b(r) \le (1 - z_{\ell})r
$$

374 According to Lemma 9, if $\ell = o(m)$, $r \sim \frac{m-\ell}{1-z_{\ell}}$ and $b(r) \sim m$.

375 Now consider the case that $\ell \ge k \log m$ for large enough $k$ such that $o_{\ell,i}r = O(\frac{1}{m^3})$. In this

376 case, $o_{\ell,i}r\omega'(o_{\ell,i}r) \sim -\frac{1}{2}o_{\ell,i}r$ and so $b(r) \sim (1-z_{\ell})r + O(\frac{1}{m^2})$. Thus $b(r) \to \infty$.

◀

377 ▶ Lemma 11. if $\epsilon = b(r)^{-\frac{4}{9}}$, we have $|\theta^3 h'''(\theta)| = m^{-\frac{1}{3}}$

378 ▶ Proof. Recall that $h'''(\theta) = -ic(re^{i\theta})$, and

$$
379 \qquad c(x) = x(1 - z_{\ell}) + \sum_{i=1}^{\ell} o_{\ell,i} x \omega'(o_{\ell,i} x) + \sum_{i=1}^{\ell} (o_{\ell,i} x)^2 \omega''(o_{\ell,i} x)
$$

380 Define $\bar{\omega}(u) := u\omega'(u) + u^2\omega''(u)$, so

$$
381 \qquad c(x) = x(1 - z_{\ell}) + \sum_{i=1}^{\ell} \bar{\omega}(o_{\ell,i} x)
$$

382 We have

$$
383 \qquad |x^k e^{\alpha x}| = |x|^k e^{\alpha \operatorname{Re}(x)} = |x|^k e^{\alpha |x| \cos(\theta)}
$$

384 If $|x| \to \infty$, we have

$$
385 \qquad \omega''(x) \sim \frac{xe^{2x}}{(e^x - 1)^3} \quad \text{and} \quad \bar{\omega}(x) \sim \frac{|x|^3 e^{2|x|} \cos(\theta)}{e^3|x| \cos(\theta)}
$$

386 which tends to zero if $|\theta| < \frac{\pi}{2} - \varepsilon$. So $\bar{\omega}$ is bounded on the cone $\{z; |\arg(z)| < \frac{\pi}{2} - \varepsilon\}$. Thus

$$
387 |c(x)| \le (1 - z_{\ell})|x| + O(\ell) \sim O(m).
$$

388 Now, define $\varepsilon = b(r)^{-\gamma} \sim m^{-\gamma}$ such that $\frac{1}{3} < \gamma < \frac{1}{2}$. In particular let $\gamma = \frac{4}{9}$ or $\varepsilon = m^{-\frac{4}{9}}$.

389 Therefore,

$$
390 \qquad |\theta^3 h'''(\theta)| = m^{-3\gamma} m = m^{\frac{1}{3}}
$$

391

◀

392 ▶ Lemma 12. if $\ell = o(m)$, then $I_2 = o(I_1)$

393 ▶ Proof. Our objective here is to bound $|S_{\ell}(re^{i\theta})|$ relatively to $S_{\ell}(r)$.

394 We have

$$
395 \qquad S_{\ell}(u) = e^{(1-z_{\ell}-\sum_{i=1}^{\ell} o_{\ell,i})u} \prod_{i=1}^{\ell} (e^{o_{\ell,i}u}-1)
$$
$e^{o_{\ell,i}u} - 1$ is a function with positive coefficients, therefore

$$|e^{o_{\ell,i}re^{i\theta}} - 1| \le e^{o_{\ell,i}r} - 1$$

Also $|e^{\alpha re^{i\theta}}| = |e^{\alpha r \cos(\theta)} + i\alpha r \sin(\theta)| = e^{\alpha r \cos(\theta)} = e^{\alpha r}e^{-\alpha r(1-\cos(\theta))}$. For $|\theta| \ge \varepsilon$ we obtain:

$$|e^{\alpha re^{i\theta}}| \le e^{\alpha r}e^{-\alpha r(1-\cos(\varepsilon))}$$

And finally we have:

$$|S_{\ell}(re^{i\theta})| \le e^{(1-z_{\ell}-\sum_{i=1}^{\ell} o_{\ell,i})r} \prod_{i=1}^{\ell} (e^{o_{\ell,i}r} - 1)e^{-(1-z_{\ell}-\sum_{i=1}^{\ell} o_{\ell,i})r(1-\cos(\varepsilon))}$$

using the definition of $S_{\ell}(r)$ the inequality simplifies into

$$|S_{\ell}(re^{i\theta})| \le S_{\ell}(r)e^{-(1-z_{\ell}-\sum_{i=1}^{\ell} o_{\ell,i})r(1-\cos(\varepsilon))} \le S_{\ell}(r)$$

So we have

$$I_2 = S_{\ell}(r)(1 + O(b(r)^{-\frac{1}{3}})) \int_{\varepsilon}^{2\pi-\varepsilon} e^{-\frac{\theta^2}{2}} b(r)$$

$$\le S_{\ell}(r)(1 + O(b(r)^{-\frac{1}{3}}))2(\pi - \varepsilon)e^{-\frac{\varepsilon^2}{2}}b(r) = S_{\ell}(r)(1 + O(b(r)^{-\frac{1}{3}}))2(\pi - \varepsilon)e^{-m\frac{\varepsilon}{3}}$$

## 7.2 Details for the OGF

In this section, we analyze the asymptotic behavior of the coefficients $c_{m,\ell}$ and $\bar{c}_{m,\ell}$ for large and small values of $\ell$, where $\hat{S}_{\ell}(u) = \sum_{m \ge 0} c_{m,\ell}u^m$ and $\bar{S}_{\ell}(u) = \sum_{m \ge 0} \bar{c}_{m,\ell}u^m$. For the sake of simplicity, the results are given in the $\mathcal{HG}(m, n, p)$ model but similar results can be stated in the $\mathcal{HG}(m, n, \pi)$ model with some additional notations.

► Lemma 13. In the $\mathcal{HG}(m, n, p)$ model with $\ell \ge \log_{\frac{1}{q}} m^{1+\epsilon}$, the coefficients satisfy

$$c_{m,\ell} = \binom{m}{\ell} \ell! o_{\ell}^{\ell} \left(1 + O\left(\frac{\log m}{m^{\epsilon}}\right)\right),$$

$$\bar{c}_{m,\ell} = \binom{m+1}{\ell+1} \ell! o_{\ell}^{\ell} \left(1 + O\left(\frac{\log m}{m^{\epsilon}}\right)\right),$$

where the constants in $O$ do not depend on $\ell$.

**Proof.** Recall that

$$\hat{S}_{\ell}(u) = u^{\ell}\ell!o_{\ell}^{\ell} \prod_{i=0}^{\ell} \frac{1}{1-u(1-z_{\ell}-io_{\ell})}$$

So,

$$u^{\ell}\ell! \frac{o_{\ell}^{\ell}}{(1-u(1-z_{\ell}-\ell o_{\ell}))^{\ell+1}} \le \hat{S}_{\ell}(u) \le u^{\ell}\ell! \frac{o_{\ell}^{\ell}}{(1-u(1-z_{\ell}))^{\ell+1}}$$

where $f(u) \le g(u)$ means the coefficients of $f$ are smaller than the coefficients of $g$. Using the following equality

$$\frac{1}{(1 - au)^{\ell + 1}} = \sum_{k \ge 0} \binom{\ell + k}{\ell} a^k u^k$$
XX:16 On the average complexity of Berge Algorithm

407 the coefficients satisfy

$$
408 \qquad \ell! o_{\ell}^{\ell} \binom{m}{\ell} (1 - z_{\ell} - \ell o_{\ell})^{m-\ell} \le c_{m,\ell} \le \ell! o_{\ell}^{\ell} \binom{m}{\ell} (1 - z_{\ell})^{m-\ell}. \qquad (3)
$$

Since $\ell \ge \log_1 m^{1+\epsilon}$, $(1-z_\ell - \ell o_\ell)^{m-\ell} = 1 + O(\log m/m^\epsilon)$ and $(1-z_\ell)^{m-\ell} = 1 + O(1/m^\epsilon)$. This
concludes the proof for $c_{m,\ell}$. For the cumulative coefficients $\bar{c}_{m,\ell}$, the bounds on $\bar{c}_{m,\ell}$ can be
reused and we obtain for all $\ell \le \ell' \le m$,

$$
\ell! o_{\ell}^{\ell} \binom{\ell'}{\ell} (1 - z_{\ell} - \ell o_{\ell})^{m-\ell} \le c_{\ell', \ell} \le \ell! o_{\ell}^{\ell} \binom{\ell'}{\ell}.
$$

409 Summing over $\ell'$ gives the announced result.

410

<figure><img src="image_7.png" /></figure>

411 The following lemma is also written for $\mathcal{H}\mathcal{G}(m, n, p)$ model. The argument used in it works
412 directly for $\mathcal{H}\mathcal{G}(m, n, \pi)$ model.

► Lemma 14. In the $\mathcal{H}\mathcal{G}(m, n, p)$ model with $\ell \le \log_{\frac{1}{q}} m^{1-\epsilon}$, the coefficients satisfy

$$
c_{m,l} = (1 - z_l)^m \left( 1 + O\left( \frac{\log m}{m^\epsilon} \right) \right),
$$

$$
\bar{c}_{m,l} = \Gamma(\frac{q}{p}) \frac{\ell!}{\Gamma(\frac{q}{p} + \ell + 1)} \frac{1}{o_{\ell}} \left( 1 + O\left(\frac{\log m}{m^{\epsilon}}\right) \right)
$$

413 **Proof.** The dominant singularity of $\hat{S}_\ell(u)$ is $\frac{1}{1-z_\ell}$. To obtain $c_{m,\ell}$, we use the Cauchy
414 coefficient formula. By choosing a circle with radius $\frac{1}{1-z_\ell-\frac{o_\ell}{2}}$ as the contour, we have

$$
\frac{1}{2\pi i} \int_{C_r} \frac{\hat{S}_{\ell}(u)}{u^{m+1}} du = [u^m] \hat{S}_{\ell}(u) + \text{Re} \left( \frac{\hat{S}_{\ell}(u)}{u^{m+1}}, u = \frac{1}{1-z_{\ell}} \right)
$$

416 and

$$
417 \quad \mathrm{Res} \left( \frac{\hat{S}_{\ell}(u)}{u^{m+1}}, u = \frac{1}{1-z_{\ell}} \right) = \mathrm{Res} \left( \frac{u^{\ell}}{u^{m+1}} \ell! o_{\ell}^{\ell} \prod_{i=0}^{\ell} \frac{1}{1-u(1-z_{\ell}-io_{\ell})}, u = \frac{1}{1-z_{\ell}} \right)
$$

$$
418 \quad \begin{aligned}
&= \ell! (1 - z_{\ell})^{m+1-\ell} o_{\ell}^{\ell} \prod_{i=1}^{\ell} \frac{1 - z_{\ell}}{io_{\ell}} \mathrm{Res} \left( \frac{1}{1 - u(1 - z_{\ell})}, u = \frac{1}{1 - z_{\ell}} \right) = -(1 - z_{\ell})^m \\
419 &\qquad - (1 - z_{\ell})^m
\end{aligned}
$$

420 So,

$$
\frac{1}{2\pi i} \int_{C_r} \frac{\hat{S}_{\ell}(u)}{u^{m+1}} du = [u^m] \hat{S}_{\ell}(u) - (1 - z_{\ell})^m
$$

422 On the other hand, $|\frac{1}{2\pi i} \int_{C_r} \frac{\hat{S}_{\ell}(u)}{u^{m+1}} du| \le \frac{\hat{S}_{\ell}(r)}{r^m}$, and we have

$$
\frac{\hat{S}_{\ell}(r)}{r^m} = \ell! r^{\ell-m} o_{\ell}^{\ell} \prod_{i=0}^{\ell} \frac{1}{1-r(1-z_{\ell}-io_{\ell})} = -\frac{1}{2} (1-z_{\ell}-\frac{o_{\ell}}{2})^{m+1} \frac{\Gamma(\frac{1}{2})}{o_{\ell} \Gamma(\ell+\frac{1}{2})} \ell!
$$

$$
\frac{1}{2\pi i} \int_{C_r} \frac{\hat{S}_{\ell}(u)}{u^{m+1}} du = O\left( (1 - z_{\ell} - \frac{o_{\ell}}{2})^m \frac{1}{o_{\ell}} r^{\frac{1}{2}} \right)
$$
To compute $\bar{c}_{m,\ell}$, we use the same argument as for computing $c_{m,\ell}$. Note that the dominant singularity of $\bar{S}_\ell(u)$ is at $u=1$. Therefore, the contour is a circle of radius $r = \frac{1}{1-\frac{z_\ell}{2}}$. Consider the term $\prod_{i=0}^\ell \frac{1}{1-u(1-z_\ell-i o_\ell)}$. We can simplify it as follows: define $\beta(u) = \frac{1-(1-z_\ell)u}{uo_\ell}$, then

426

427

428

429

430

$$ \prod_{i=0}^{\ell} \frac{1}{1 - u(1 - z_{\ell} - i o_{\ell})} = \frac{1}{(uo_{\ell})^{\ell+1}} \prod_{i=0}^{\ell} \frac{1}{\beta(u) + i} = \frac{1}{(uo_{\ell})^{\ell+1}} \frac{\Gamma(\beta(u))}{\Gamma(\beta(u) + \ell + 1)} $$

431

Note that $\beta(1) = \frac{q}{p}$, so we have:

432

$$ \mathrm{Res}(\frac{\bar{S}_\ell(u)}{u^{m+1}}, u=1) = \ell! \frac{\Gamma(\frac{q}{p})}{o_\ell \Gamma(\frac{q}{p} + \ell + 1)} \mathrm{Res}(\frac{1}{1-u}, u=1) = -\ell! \frac{\Gamma(\frac{q}{p})}{o_\ell \Gamma(\frac{q}{p} + \ell + 1)} $$

433

Thus

434

$$ \frac{1}{2\pi i} \int_{C_r} \frac{\bar{S}_\ell(u)}{u^{m+1}} du = [u^m] \hat{S}_\ell(u) - \frac{\ell!}{o_\ell} \frac{\Gamma(\frac{q}{p})}{\Gamma(\frac{q}{p} + \ell + 1)} $$

435

But $|\frac{1}{2\pi i} \int_{C_r} \frac{\bar{S}_\ell(u)}{u^{m+1}} du| \le \frac{\bar{S}_\ell(r)}{r^m}$ and

436

$$ \frac{\bar{S}_\ell(r)}{r^m} = \ell! o_\ell^\ell (1 - \frac{z_\ell}{2})^{m+2} \frac{\Gamma(\frac{q}{2p})}{z_\ell o_\ell^{\ell+1} \Gamma(\frac{q}{2p} + \ell + 1)} $$

437

<figure><img src="image_8.png" /></figure>

**► Lemma 15.** In the $\mathcal{H}\mathcal{G}(m, n, p)$ model with $\log_{\frac{1}{q}} m^{1-\epsilon} \le \ell \le \log_{\frac{1}{q}} m^{1+\epsilon}$, the cumulative sums satisfy

$$ \ell! o_{\ell}^{\ell} \binom{j_0}{\ell} (1 - z_{\ell} - \ell o_{\ell})^{j_0 - \ell} \le \bar{c}_{m, \ell} \le (m - \ell) \ell! o_{\ell}^{\ell} \binom{j_1}{\ell} (1 - z_{\ell})^{j_1 - \ell} $$

where $j_0$ and $j_1$ are the indexes such that the bounds in Inequality (3) are maximal. In particular, we have

$$ j_0 = \min \left( m, \left\lfloor \frac{\ell}{z_{\ell} + \ell o_{\ell}} \right\rfloor \right), \quad j_1 = \min \left( m, \left\lfloor \frac{\ell}{z_{\ell}} \right\rfloor \right). $$

**Proof.** The proofs for the lower and upper bounds are similar. The inequalities in(3) give

$$ \ell! o_{\ell}^{\ell} \max_{i=\ell \dots m} \binom{i}{\ell} (1 - z_{\ell} - \ell o_{\ell})^{i-\ell} \le \bar{c}_{m, \ell} \le (m-\ell) \ell! o_{\ell}^{\ell} \max_{i=\ell \dots m} \binom{i}{\ell} (1 - z_{\ell})^{i-\ell}. $$

438

439

440

Studying the ratio between two consecutive elements in the max, it can be proved that the sequences are increasing for $j \le j_0$ or $j \le j_1$ and then decreasing (if $j_0 \ne m$ or $j_1 \ne m$). This concludes the proof.

<figure><img src="image_9.png" /></figure>

## 7.3 Details for the average number of minimal transversals

441

Let $\ell' = \log_{\frac{1}{p}}(m^{2(\alpha+1)})$ and $av(n, m, \ell) = \binom{n}{\ell} m![u^m]S_\ell(u)$. The average number of minimal transversals is

$$ \sum_{\ell=1}^{\min\{m,n\}} av(n, m, \ell) $$
XX:18 On the average complexity of Berge Algorithm

Assuming that that $n = m^\alpha$ with $\alpha < 1$, we split the formula into two parts:

$$ \sum_{\ell=1}^{\ell'-1} av(n, m, \ell) + \sum_{\ell=\ell'}^{n} av(n, m, \ell) $$

The two following lemmas gives the asymptotic.

► Lemma 16. The asymptotic of the first sum is equal to $av(n, m, ⌊j⌋) + av(n, m, ⌊j + 1⌋) + av(n, m, ⌊j + 2⌋)$

Proof. there is a unique constant $\kappa$ such that

$$ \alpha + \log_{\frac{1}{1-p}} \left( \frac{1 - e^{-(1-p)\kappa}}{1 - e^{-\kappa}} \right) = 0 $$

we define the real value $j$ such that $p(1-p)^{j-1} = \kappa$. Let $r_\ell$ be the solution of $a(r_\ell) = m$. We study the ratio:

$$ \tilde{R}(n, m, \ell) = \frac{av(n, m, \ell + 1)}{av(n, m, \ell)} = \frac{n - \ell}{\ell + 1} \frac{S_{\ell+1}(r_{\ell+1})}{S_\ell(r_\ell)} \left( \frac{r_\ell}{r_{\ell+1}} \right)^m $$

It can be proven that:

■ $\tilde{R}(n, m, ⌊j⌋) \ge 1$

■ $\tilde{R}(n, m, ⌊j + 1⌋) \le 1$

■ for all $\ell < ⌊j⌋$, $\tilde{R}(n, m, \ell)$ tends to infinity uniformly in $m$

■ for all $\ell > ⌊j + 1⌋$, $\tilde{R}(n, m, \ell)$ tends to 0 uniformly in $m$.

450

<figure><img src="image_10.png" /></figure>

► Lemma 17. The second sum is equal to $O(\frac{1}{m})$

Proof. — first we prove that $\binom{n}{\ell'}[u^m]S_{\ell'}(u) = O(\frac{1}{m^{\alpha+1}})$. We have

$$ \begin{align*} \binom{n}{\ell'}[u^m]S_{\ell'}(u) &\sim \binom{n}{\ell'} \frac{m!}{(m-\ell)!} p^{\ell'} (1-p)^{\ell'(\ell'-1)} \\ &\le n^{\ell'} m^{\ell'} (1-p)^{\ell'(\ell'-1)} \\ &\le \frac{m^{(\alpha+1)\ell'}}{m^{2(\alpha+1)(\ell'-1)}} \\ &\le \frac{1}{m^{\alpha+1}} \end{align*} $$

■ Then we show that $\frac{av(n,m,\ell+1)}{av(n,m,\ell)} < 1$, for all $\ell \ge \ell'$. For all $\ell \in \{1, \dots, n-1\}$, we have

$$ \frac{av(n, m, \ell + 1)}{av(n, m, \ell)} = \frac{p(n - \ell)(m - \ell)(1 - p)^{2\ell}}{(\ell + 1)} \le pnm(1 - p)^{2\ell} $$

For all value $\ell \ge \ell'$ we obtain

$$ \frac{av(n, m, \ell + 1)}{av(n, m, \ell)} \le p $$

Therefore we have the $\sum_{\ell=\ell'}^{n} av(n, m, \ell) = O(\frac{1}{m})$.

458

<figure><img src="image_11.png" /></figure>
## 7.4 Details for the average case complexity of the Berge algorithm

459

460

461

462

This section is devoted to the proof of Proposition 5 on the average case complexity of the Berge algorithm. By hypothesis, we have $n = m^\alpha$ with $\alpha < 1$. The average complexity satisfies the upper bound

463

$$ \mathbb{E}_p[B(\mathcal{H})] \le n \cdot m \cdot \min\{n, m\} \sum_{i=1}^{m} \mathbb{E}_{\pi}[\mathrm{Tr}_{i,n}] \le m^{2\alpha+1} \sum_{\ell=1}^{n} \binom{n}{\ell} \bar{c}_{m,\ell} $$

464

465

466

with $\bar{c}_{m,\ell} = \sum_{i=\ell}^{m} c_{m,\ell}$. According to Proposition 3, the sum is split into three parts: $\ell \le \ell^-$, $\ell \ge \ell^+$ and $\ell^- \le \ell \le \ell^+$ with $\ell^- = \log_{\frac{1}{q}} m^{1-\epsilon}$ and $\ell^+ = \log_{\frac{1}{q}} m^{1+\epsilon}$ for an arbitrary fixed positive $\epsilon$.

467

► Lemma 18. The first and third sums satisfy

468

$$ \sum_{\ell=1}^{\ell^-} \binom{n}{\ell} \bar{c}_{m,\ell} = \binom{n}{\ell^-} \bar{c}_{m,\ell^-} (1+o(1)), \quad \text{and} \quad \sum_{\ell=\ell^+}^{n} \binom{n}{\ell} \bar{c}_{m,\ell} = \binom{n}{\ell^+} \bar{c}_{m,\ell^+} (1+o(1)). $$

469

470

471

472

473

**Proof.** The proof is similar in the two cases. First the ratio $R_\ell = \binom{n}{\ell+1} \bar{c}_{m,\ell+1}/\binom{n}{\ell} \bar{c}_{m,\ell}$ is calculated using the equivalences of Proposition 3 and we prove it is decreasing. After, we show that $R_{\ell^-}$ tends to infinity whereas $R_{\ell^+}$ tends to 0. Then we can conclude and the $o(1)$ can be replaced by $O(1/R_{\ell^-})$ for the first sum and $O(R_{\ell^+})$ for the second one. Indeed the equality in Proposition 3 gives for $\ell \le \ell^-$ and $\ell \ge \ell^+$

474

$$ R_{\ell} = \frac{n-\ell}{q+\ell+1} \frac{1}{q} \left( 1 + \mathcal{O}\left( \frac{\log m}{m^{\epsilon}} \right) \right), \quad R_{\ell} = \frac{(n-\ell)(m-\ell)}{\ell+2} pq^{2\ell} \left( 1 + \mathcal{O}\left( \frac{\log m}{m^{\epsilon}} \right) \right). $$

475

476

It proves that the ratio $R_\ell$ is decreasing with $\ell$ in both cases. The ratio $R_{\ell^-}$ is a $\Theta(\frac{n}{\log m})$ which tends to $+\infty$. The ratio $R_{\ell^+}$ is a $\Theta(\frac{1}{m^{1-\alpha+2\epsilon}\log m})$ which tends to 0 for $\epsilon$ small enough. By induction on $\ell$, $\binom{n}{\ell} \bar{c}_{m,\ell} \le \binom{n}{\ell^-} \bar{c}_{m,\ell^-} R_{\ell^-}^{\ell-\ell^-}$ and $\binom{n}{\ell} \bar{c}_{m,\ell} \le \binom{n}{\ell^+} \bar{c}_{m,\ell^+} R_{\ell^+}^{\ell-\ell^+}$. Summing over $\ell$ gives the two assertions. ◀

477

478

Note that Lemma 18 entails that the asymptotic in the complete sum is given by the asymptotic over the $\ell$ in the intermediate range $\ell^- \le \ell \le \ell^+$. Using once more the upper bound in Proposition 3, we obtain

482

$$ \begin{aligned} \sum_{\ell=1}^{n} \binom{n}{\ell} \bar{c}_{m,\ell} &= (1+o(1)) \sum_{\ell=\ell^-}^{\ell^+} \binom{n}{\ell} \bar{c}_{m,\ell} \\ &\le (1+o(1)) m \sum_{\ell=\ell^-}^{\ell^+} \binom{n}{\ell} \ell! o_{\ell}^{\ell} \binom{j_{\ell}}{\ell} (1-z_{\ell})^{j_{\ell}-\ell} \end{aligned} \quad (4) $$

483

with $j_\ell = j_\ell(m, \ell) = \min(m, \lfloor \frac{\ell}{z_\ell} \rfloor)$. We now deal with the asymptotic of the right hand side, using once more the upper bound in Proposition 3. For this, we consider once more the ratio $R_\ell$ of two successive elements,

$$ R_{\ell} = \frac{n-\ell}{\ell+1} pq^{2\ell} \frac{j_{\ell+1}!}{(j_{\ell+1}-\ell-1)!} \frac{(j_{\ell}-\ell)!}{j_{\ell}!} \frac{(1-z_{\ell+1})^{j_{\ell+1}-\ell-1}}{(1-z_{\ell})^{j_{\ell}-\ell}}. $$

484
**XX:20 On the average complexity of Berge Algorithm**

**► Lemma 19.** The ratio $R_\ell$ is decreasing and the maximum value in the sum (4) is obtained for $\ell = \log_\frac{1}{q}(m) - \log_\frac{1}{q}(\ln m) - \log_\frac{1}{q}(\frac{1-\alpha}{p}) + o(1)$ when $\alpha \ge 1 - \frac{p}{\ln(1-p)}$. In particular, we have

$$ \sum_{\ell=1}^{n} \binom{n}{\ell} \bar{c}_{m,\ell} \le (1+o(1))m(\ell^{+} - \ell^{-}) \binom{n}{\ell} \ell! o_{\ell}^{\ell} \binom{m}{\ell} (1-z_{\ell})^{m-\ell}. $$

**Proof.** To study the ratio, it is necessary to distinguish the case $j_\ell < m$ and the case $j_\ell = m$. Though, in both cases, the ratio is decreasing. The $\ell$ given in the lemma only comes from exact calculations. Note that the condition on $\alpha$ ensures that $j_\ell = m$. ◀

**7.5 Details for the Poisson-Mellin-Newton Cycle**

The generating function is in the following form:

$$ S_{\ell}(u) = e^{(1-(1-p)^{\ell})u} \left(1 - e^{-p(1-p)^{\ell-1}u}\right)^{\ell} $$

The Poisson generating function is $P_l(u) = e^{-u}S_l(u) = e^{-u(1-p)^\ell} \left(1 - e^{-p(1-p)^{\ell-1}u}\right)^\ell$

The Mellin transform is as follows:

$$ M_l(s) = \frac{1}{(1-p)^{sl}} \int_0^{\infty} v^{s-1} e^{-v} \left(1 - e^{-\frac{p}{1-p}v}\right)^l dv $$

Using the Binomial theorem we have:

$$ M_l(s) = \frac{1}{(1-p)^{sl}} \int_0^{\infty} v^{s-1} e^{-v} \left( \sum_{k=0}^{l} \binom{l}{k} (-1)^{l-k} e^{-\frac{(l-k)p}{1-p}} v \right) dv $$

$$ = \sum_{k=0}^{l} \binom{l}{k} (-1)^{l-k} \frac{1}{(1-p)^{sl}} \int_{0}^{\infty} v^{s-1} e^{-v \left( \frac{1-p+lp-kp}{1-p} \right)} dv = $$

Then by changing the variable $v(\frac{1-p+lp-kp}{1-p}) = u$ we have $\int_0^\infty v^{s-1}e^{-v(\frac{1-p+lp-kp}{1-p})}dv = \int_0^\infty u^{s-1}e^{-u(\frac{1-p+lp-kp}{1-p})}du = (\frac{1-p}{1-p+lp-kp})^s \Gamma(s)$ and therefore

$$ M_l(s) = \sum_{k=0}^{l} (-1)^{l-k} \binom{l}{k} \frac{\Gamma(s)}{(1-p)^{(l-1)s}(1-p+lp-kp)^s} $$

According to Poisson-Mellin-Newton cycle, we know that the coefficients of the p.g.f. are obtained as follows by simplifying the Nørlund-Rice Integral:

$$ C_{m,l} = \frac{1}{2\pi i} \int_{\Lambda} \frac{\Gamma(m+1)}{\Gamma(m+s+1)} M_l(s) ds $$

But

$$ \int_{\Lambda} \frac{M_l(s)}{\Gamma(m+s+1)} ds = \sum_{k=0}^{l} (-1)^{l-k} \binom{l}{k} \int_{\Lambda} \frac{ds}{(1-p)^{(l-1)s}(1-p+lp-kp)^s(s)(s+1)\cdots(s+m)} $$

Let

$$ F(s) = \frac{1}{(1-p)^{(l-1)s}(1-p+lp-kp)^s(s)(s+1)\cdots(s+m)} $$
then according to the Residue Theorem we have:

$$ \int_{\Lambda} \frac{ds}{(1-p)^{(l-1)s}(1-p+lp-kp)^s(s)(s+1)\cdots(s+m)} = 2\pi i \sum_{j=0}^{m} \mathrm{Res}[F(s), s = -j] $$

But

$$ \mathrm{Res}[F(s), s = -j] = \frac{(-1)^j}{j!(m-j)!} \left( \frac{1}{(1-p)^{(l-1)}(1-p+lp-kp)} \right)^{-j} $$

So

$$ \sum_{j=0}^{m} \mathrm{Res}[F(s), s = -j] = \frac{1}{m!} \sum_{j=0}^{m} \binom{m}{j} (-1)^j ((1-p)^{(l-1)}(1-p+lp-kp))^j = \frac{1}{m!} (1 - (1-p)^{l-1}(1-p+lp-kp))^m $$

Thus

$$ 2\pi i \sum_{j=0}^{m} \mathrm{Res}[F(s), s = -j] = \frac{2\pi i}{m!} (1 - (1-p)^{l-1}(1-p+lp-kp))^m $$

Therefore $C_{m,l}$ is as follows:

$$ \begin{aligned} C_{m,l} &= \sum_{k=0}^{l} (-1)^{l-k} \binom{l}{k} (1 - [(1-p)^{l-1}(1-p+lp-kp)])^m \\ &= \sum_{k=0}^{l} (-1)^{l-k} \binom{l}{k} \left[ \sum_{i=0}^{m} \binom{m}{i} (1 - (1-p)^l - lp(1-p)^{l-1})^{m-i} (p(1-p)^{l-1}k)^i \right] \\ &= \sum_{i=0}^{m} \binom{m}{i} (1 - (1-p)^l - lp(1-p)^{l-1})^{m-i} (p(1-p)^{l-1})^i \left( \sum_{k=0}^{l} (-1)^{l-k} \binom{l}{k} k^i \right) \\ &= \sum_{i=0}^{m} \binom{m}{i} l! \binom{i}{l} (1 - (1-p)^l - lp(1-p)^{l-1})^{m-i} (p(1-p)^{l-1})^i \end{aligned} \quad (5) $$

in which $\binom{i}{l}$ is Stirling numbers of the second kind.

References

1. Rakesh Agrawal, Tomasz Imieliński, and Arun Swami. Mining association rules between sets of items in large databases. In *Proceedings of the 1993 ACM SIGMOD international conference on Management of data*, pages 207–216, 1993.

2. James Bailey, Thomas Manoukian, and Kotagiri Ramamohanarao. A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns. In *Third IEEE International Conference on Data Mining*, pages 485–488. IEEE, 2003.

3. James Bailey and Zhou Zhu. Fast discovery of interesting collections of web services. In *2006 IEEE/WIC/ACM International Conference on Web Intelligence (WI 2006 Main Conference Proceedings) (WI’06)*, pages 152–160. IEEE, 2006.

4. Alexandre Bazin, Laurent Beaudou, Giacomo Kahn, and Kaveh Khoshkhah. Bounding the number of minimal transversals in tripartite 3-uniform hypergraphs. *Discrete Mathematics & Theoretical Computer Science*, 23(Special issues), 2023.
XX:22 On the average complexity of Berge Algorithm

537

5 Claude Berge. Hypergraphs. Elsevier, 3rd edition, 1989.

538

6 Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Leonid Khachiyan. Generating maximal independent sets for hypergraphs with bounded edge-intersections. In Latin American Symposium on Theoretical Informatics, pages 488–498. Springer, 2004.

539

540

7 Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan, and Kazuhisa Makino. An intersection inequality for discrete distributions and related generation problems. In International Colloquium on Automata, Languages, and Programming, pages 543–555. Springer, 2003.

541

542

543

544

8 Endre Boros and Vladimir Gurvich. On nash-solvability in pure stationary strategies of finite games with perfect information which may have cycles. Mathematical social sciences, 46(2):207–241, 2003.

545

546

547

9 Andreas Brandstädt, Van Bang Le, and Jeremy P Spinrad. Graph classes: a survey. SIAM, 1999.

548

549

10 Peter Damaschke. Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theoretical Computer Science, 351(3):337–350, 2006.

550

551

11 Julien David, Loïck Lhote, Arnaud Mary, and François Rioult. An average study of hypergraphs and their minimal transversals. Theoretical Computer Science, 596:124–141, 2015.

552

553

12 Pierpaolo Degano. Automata, Languages and Programming: 24th International Colloquium, ICALP'97, Bologna, Italy, July 7-11, 1997, Proceedings, volume 24. Springer Science & Business Media, 1997.

554

555

556

13 Guozhu Dong and Jinyan Li. Mining border descriptions of emerging patterns from dataset pairs. Knowledge and Information Systems, 8:178–202, 2005.

557

558

14 Jean-Guillaume Dumas, Frank Heckenbach, David Saunders, and Volkmar Welker. Computing simplicial homology based on efficient smith normal form algorithms. In Algebra, Geometry and Software Systems, pages 177–206. Springer, 2003.

559

560

561

15 Thomas Eiter and Georg Gottlob. Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing, 24(6):1278–1304, 1995.

562

563

16 Thomas Eiter and Georg Gottlob. Hypergraph transversal computation and related problems in logic and ai. In European Workshop on Logics in Artificial Intelligence, pages 549–564. Springer, 2002.

564

565

566

17 Thomas Eiter, Georg Gottlob, and Kazuhisa Makino. New results on monotone dualization and generating hypergraph transversals. In Proceedings of the thirt-y-fourth annual ACM symposium on Theory of computing, pages 14–22, 2002.

567

568

569

18 P ERdDs and A R&wi. On random graphs i. Publ. math. debrecen, 6(290-297):18, 1959.

570

19 Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. cambridge University press, 2009.

571

572

20 Michael L Fredman and Leonid Khachiyan. On the complexity of dualization of monotone disjunctive normal forms. Journal of algorithms, 21(3):618–628, 1996.

573

574

21 Hector Garcia-Molina and Daniel Barbara. How to assign votes in a distributed system. Journal of the ACM (JACM), 32(4):841–860, 1985.

575

576

22 Daya Ram Gaur and Ramesh Krishnamurti. Average case self-duality of monotone boolean functions. In Advances in Artificial Intelligence: 17th Conference of the Canadian Society for Computational Studies of Intelligence, Canadian AI 2004, London, Ontario, Canada, May 17-19, 2004. Proceedings 17, pages 322–338. Springer, 2004.

577

578

579

580

23 Dimitrios Gunopulos, Roni Khardon, Heikki Mannila, Sanjeev Saluja, Hannu Toivonen, and Ram Sewak Sharma. Discovering all most specific sentences. ACM Transactions on Database Systems (TODS), 28(2):140–174, 2003.

581

582

583

24 Dimitrios Gunopulos, Heikki Mannila, Roni Khardon, and Hannu Toivonen. Data mining, hypergraph transversals, and machine learning. In Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pages 209–216, 1997.

584

585

586

25 Matthias Hagen. Lower bounds for three algorithms for transversal hypergraph generation. Discrete Applied Mathematics, 157(7):1460–1469, 2009.

587

588
589

26 Utz-Uwe Haus, Steffen Klamt, and Tamon Stephen. Computing knock-out strategies in metabolic networks. *Journal of Computational Biology*, 15(3):259-268, 2008.

590

27 Céline Hébert, Alain Bretto, and Bruno Crémilleux. A data mining formalization to improve hypergraph minimal transversal computation. *Fundamenta Informaticae*, 80(4):415-433, 2007.

591

592

28 David S Johnson, Mihalis Yannakakis, and Christos H Papadimitriou. On generating all maximal independent sets. *Information Processing Letters*, 27(3):119-123, 1988.

593

594

29 Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, and Lhouari Nourine. On the enumeration of minimal dominating sets and related notions. *SIAM Journal on Discrete Mathematics*, 28(4):1916-1929, 2014.

595

596

597

30 Naouel Karam, Serge Linckels, and Christoph Meinel. Semantic composition of lecture subparts for a personalized e-learning. In *The Semantic Web: Research and Applications: 4th European Semantic Web Conference, ESWC 2007, Innsbruck, Austria, June 3-7, 2007. Proceedings 4*, pages 716-728. Springer, 2007.

598

599

600

601

31 Dimitris J Kavvadias and Elias C Stavropoulos. An efficient algorithm for the transversal hypergraph generation. *J. Graph Algorithms Appl.*, 9(2):239-264, 2005.

602

603

32 Dogan Kesdogan and Lexi Pimenidis. The hitting set attack on anonymity protocols. In *International Workshop on Information Hiding*, pages 326-339. Springer, 2004.

604

605

33 Leonid Khachiyan. Transversal hypergraphs and families of polyhedral cones. *Advances in Convex Analysis and Global Optimization: Honoring the Memory of C. Caratheodory (1873-1950)*, pages 105-118, 2001.

606

607

608

34 Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Vladimir Gurvich. An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation. *Discrete Applied Mathematics*, 154(16):2350-2372, 2006.

609

610

611

35 Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Vladimir Gurvich. Generating all minimal integral solutions to and-or systems of monotone inequalities: Conjunctions are simpler than disjunctions. *Discrete applied mathematics*, 156(11):2020-2034, 2008.

612

613

614

36 Steffen Klamt, Julio Saez-Rodriguez, and Ernst D Gilles. Structural and functional analysis of cellular networks with cellnetanalyzer. *BMC systems biology*, 1(1):1-13, 2007.

615

616

37 Heikki Mannila and Kari-Jouko Räihä. On the complexity of inferring functional dependencies. *Discrete Applied Mathematics*, 40(2):237-243, 1992.

617

618

38 Ronald C Read. Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations. In *Annals of discrete mathematics*, volume 2, pages 107-120. Elsevier, 1978.

619

620

621

39 Saswati Sarkar and Kumar N Sivarajan. Hypergraph models for cellular mobile communication systems. *IEEE Transactions on Vehicular Technology*, 47(2):460-471, 1998.

622

623

40 Ken Takata. A worst-case analysis of the sequential method to list the minimal hitting sets of a hypergraph. *SIAM Journal on Discrete Mathematics*, 21(4):936-946, 2008.

624

625