SCIENCE@home

Property Testing in Bounded Degree Hypergraphs

Hugo Aaronson,Gaia Carenini,Atreyi Chanda

Published 2025 in Electron. Colloquium Comput. Complex.

ABSTRACT

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 $\Omega(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 $\Theta(n)$ hyperedges from any hypergraph satisfying the property, but where violations of the latter cannot be detected in any neighborhood of $o(n)$ vertices.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-48 of 48 references · Page 1 of 1

CITED BY