Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914771942506496 |
|---|---|
| author | Dell, Holger Lapinskas, John Meeks, Kitty |
| author_facet | Dell, Holger Lapinskas, John Meeks, Kitty |
| contents | We study a query model of computation in which an n-vertex k-hypergraph can be accessed only via its independence oracle or via its colourful independence oracle, and each oracle query may incur a cost depending on the size of the query. In each of these models, we obtain oracle algorithms to approximately count the hypergraph's edges, and we unconditionally prove that no oracle algorithm for this problem can have significantly smaller worst-case oracle cost than our algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_03874 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Nearly optimal independence oracle algorithms for edge estimation in hypergraphs Dell, Holger Lapinskas, John Meeks, Kitty Computational Complexity Data Structures and Algorithms We study a query model of computation in which an n-vertex k-hypergraph can be accessed only via its independence oracle or via its colourful independence oracle, and each oracle query may incur a cost depending on the size of the query. In each of these models, we obtain oracle algorithms to approximately count the hypergraph's edges, and we unconditionally prove that no oracle algorithm for this problem can have significantly smaller worst-case oracle cost than our algorithms. |
| title | Nearly optimal independence oracle algorithms for edge estimation in hypergraphs |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2211.03874 |