Global certification via perfect hashing
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916117027487744 |
|---|---|
| author | Bousquet, Nicolas Feuilloley, Laurent Zeitoun, Sébastien |
| author_facet | Bousquet, Nicolas Feuilloley, Laurent Zeitoun, Sébastien |
| contents | In this work, we provide an upper bound for global certification of graph homomorphism, a generalization of graph coloring. In certification, the nodes of a network should decide if the network satisfies a given property, thanks to small pieces of information called certificates. Here, there is only one global certificate which is shared by all the nodes, and the property we want to certify is the existence of a graph homomorphism to a given graph.
For bipartiteness, a special case of graph homomorphism, Feuilloley and Hirvonen proved in~\cite{FeuilloleyH18} some upper and lower bounds on the size of the optimal certificate, and made the conjecture that their lower bound could be improved to match their upper bound. We prove that this conjecture is false: their lower bound was in fact optimal, and we prove it by providing the matching upper bound using a known result of perfect hashing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_03849 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Global certification via perfect hashing Bousquet, Nicolas Feuilloley, Laurent Zeitoun, Sébastien Distributed, Parallel, and Cluster Computing Data Structures and Algorithms In this work, we provide an upper bound for global certification of graph homomorphism, a generalization of graph coloring. In certification, the nodes of a network should decide if the network satisfies a given property, thanks to small pieces of information called certificates. Here, there is only one global certificate which is shared by all the nodes, and the property we want to certify is the existence of a graph homomorphism to a given graph. For bipartiteness, a special case of graph homomorphism, Feuilloley and Hirvonen proved in~\cite{FeuilloleyH18} some upper and lower bounds on the size of the optimal certificate, and made the conjecture that their lower bound could be improved to match their upper bound. We prove that this conjecture is false: their lower bound was in fact optimal, and we prove it by providing the matching upper bound using a known result of perfect hashing. |
| title | Global certification via perfect hashing |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.03849 |