Affordable Access

Publisher Website

On recognizing graph properties from adjacency matrices

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
3
Issue
3
Identifiers
DOI: 10.1016/0304-3975(76)90053-0

Abstract

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(0 d ) ≠ P(1 d ) 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 v 2 16 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.

There are no comments yet on this publication. Be the first to share your thoughts.