Elsevier

Theoretical Computer Science

Volume 3, Issue 3, December 1976, Pages 371-384
Theoretical Computer Science

On recognizing graph properties from adjacency matrices

https://doi.org/10.1016/0304-3975(76)90053-0Get rights and content
Under an Elsevier user license
open archive

Abstract

A conjecture of Aanderaa and Rosenberg [15] motivates this work. We investigate the maximum number C(P) of arguments of P that must be tested in order to compute P, a Boolean function of d Boolean arguments. We present evidence for the general conjecture that C(P) = d whenever P(0d) ≠ P(1d) and P is invariant under a transitive permutation group acting on the arguments. A non-constructive argument (not based on the construction of an “oracle”) settles this question for d a prime power. We use this result to prove the Aanderaa-Rosenberg conjecture: at least v216 entries of the adjacency matrix of a v-vertex undirected graph G must be examined in the worst case to determine if G has any given non-trivial monotone graph property.

Cited by (0)

This work was supported by IRIA-Laboria, 78150 Rocquencourt, France, and by the National Science Foundation under NSF grant number GJ43634X, contract number DCR74-12997-A01, and NSF grant no. MCS76-14294.