ALCOMFT-TR-01-133

Artur Czumaj and Christian Sohler
Testing Hypergraph Coloring
Paderborn. Work package 4. May 2001.

Abstract: In this paper we initiate the study of testing properties of hypergraphs. The goal of property testing is to distinguish between the case whether a given object has a certain property or is 'far away' from the property. We prove that the fundamental problem of l-colorability of k-uniform hypergraphs can be tested in time independent of the size of the hypergraph. We present a testing algorithm that examines only (kl/epsilon)^O(k) entries of the adjacency matrix of the input hypergraph, where epsilon is a distance parameter independent of the size of the hypergraph. Notice that this algorithm tests only a constant number of entries in the adjacency matrix provided that l,k and epsilon are constant.

Postscript file: ALCOMFT-TR-01-133.ps.gz (74 kb).