Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2409.09155 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913526338027520 |
|---|---|
| author | Sumnicht, Christopher Weber, Jamison W. Giriyan, Dhanush R. Sen, Arunabha |
| author_facet | Sumnicht, Christopher Weber, Jamison W. Giriyan, Dhanush R. Sen, Arunabha |
| contents | Significant work has been done on computing the ``average'' optimal solution value for various $\mathsf{NP}$-complete problems using the Erdös-Rényi model to establish \emph{critical thresholds}. Critical thresholds define narrow bounds for the optimal solution of a problem instance such that the probability that the solution value lies outside these bounds vanishes as the instance size approaches infinity. In this paper, we extend the Erdös-Rényi model to general hypergraphs on $n$ vertices and $M$ hyperedges. We consider the problem of determining critical thresholds for the largest cardinality matching, and we show that for $M=o(1.155^n)$ the size of the maximum cardinality matching is almost surely 1. On the other hand, if $M=Θ(2^n)$ then the size of the maximum cardinality matching is $Ω(n^{\frac12-γ})$ for an arbitrary $γ>0$. Lastly, we address the gap where $Ω(1.155^n)=M=o(2^n)$ empirically through computer simulations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_09155 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Critical Thresholds for Maximum Cardinality Matching on General Hypergraphs Sumnicht, Christopher Weber, Jamison W. Giriyan, Dhanush R. Sen, Arunabha Discrete Mathematics Combinatorics Significant work has been done on computing the ``average'' optimal solution value for various $\mathsf{NP}$-complete problems using the Erdös-Rényi model to establish \emph{critical thresholds}. Critical thresholds define narrow bounds for the optimal solution of a problem instance such that the probability that the solution value lies outside these bounds vanishes as the instance size approaches infinity. In this paper, we extend the Erdös-Rényi model to general hypergraphs on $n$ vertices and $M$ hyperedges. We consider the problem of determining critical thresholds for the largest cardinality matching, and we show that for $M=o(1.155^n)$ the size of the maximum cardinality matching is almost surely 1. On the other hand, if $M=Θ(2^n)$ then the size of the maximum cardinality matching is $Ω(n^{\frac12-γ})$ for an arbitrary $γ>0$. Lastly, we address the gap where $Ω(1.155^n)=M=o(2^n)$ empirically through computer simulations. |
| title | Critical Thresholds for Maximum Cardinality Matching on General Hypergraphs |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2409.09155 |