Property Testing in Bounded Degree Hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915195806285824 |
|---|---|
| author | Aaronson, Hugo Carenini, Gaia Chanda, Atreyi |
| author_facet | Aaronson, Hugo Carenini, Gaia Chanda, Atreyi |
| contents | We extend the bounded degree graph model for property testing introduced by Goldreich and Ron (Algorithmica, 2002) to hypergraphs. In this framework, we analyse the query complexity of three fundamental hypergraph properties: colorability, $k$-partiteness, and independence number. We present a randomized algorithm for testing $k$-partiteness within families of $k$-uniform $n$-vertex hypergraphs of bounded treewidth whose query complexity does not depend on $n$. In addition, we prove optimal lower bounds of $Ω(n)$ on the query complexity of testing algorithms for $k$-colorability, $k$-partiteness, and independence number in $k$-uniform $n$-vertex hypergraphs of bounded degree. For each of these properties, we consider the problem of explicitly constructing $k$-uniform hypergraphs of bounded degree that differ in $Θ(n)$ hyperedges from any hypergraph satisfying the property, but where violations of the latter cannot be detected in any neighborhood of $o(n)$ vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_18382 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Property Testing in Bounded Degree Hypergraphs Aaronson, Hugo Carenini, Gaia Chanda, Atreyi Computational Complexity Discrete Mathematics We extend the bounded degree graph model for property testing introduced by Goldreich and Ron (Algorithmica, 2002) to hypergraphs. In this framework, we analyse the query complexity of three fundamental hypergraph properties: colorability, $k$-partiteness, and independence number. We present a randomized algorithm for testing $k$-partiteness within families of $k$-uniform $n$-vertex hypergraphs of bounded treewidth whose query complexity does not depend on $n$. In addition, we prove optimal lower bounds of $Ω(n)$ on the query complexity of testing algorithms for $k$-colorability, $k$-partiteness, and independence number in $k$-uniform $n$-vertex hypergraphs of bounded degree. For each of these properties, we consider the problem of explicitly constructing $k$-uniform hypergraphs of bounded degree that differ in $Θ(n)$ hyperedges from any hypergraph satisfying the property, but where violations of the latter cannot be detected in any neighborhood of $o(n)$ vertices. |
| title | Property Testing in Bounded Degree Hypergraphs |
| topic | Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2502.18382 |