Abstract
The complexity of a digraph property is the number of entries of the adjacency matrix which must be examined by a decision tree algorithm to recognize the property in the worst case, Aanderaa and Rosenberg conjectured that there is a constantε such that every digraph property which is monotone (not destroyed by the deletion of edges) and nontrivial (holds for some but not all digraphs) has complexity at leastεv 2 wherev is the number of nodes in the digraph. This conjecture was proved by Rivest and Vuillemin and a lower bound ofv 2/4−o(v 2) was subsequently found by Kahn, Saks, and Sturtevant. Here we show a lower bound ofv 2/2−o(v 2). We also prove that a certain class of monotone, nontrivial bipartite digraph properties is evasive (requires that every entry in the adjacency matrix be examined in the worst case).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
G. H.Hardy and E. M.Wright,An Introduction to the Theory of Numbers, Clarendon Press,1938.
J. Kahn, M. Saks andD. Sturtevant, A topological approach to evasiveness,Combinatorica,4 (4) (1984), 297–306.
D. J. Kleitman andD. J. Kwiatkowski, Further Results on the Aanderaa-Rosenberg Conjecture,J. Combinatorial Theory,B 28 (1980), 85–95.
J.Munkres,Elements of Algebraic Topology (1984).
R. Oliver, Fixed-point sets of group actions on finite acyclic complexes,Comment. Math. Helv.,50 (1975), 155–177.
R. Rivest andS. Vuillemin, On recognizing graph properties from adjacency matrices,Theor. Comp. Sci.,3 (1976), 371–384.
A. L. Rosenberg, On the time required to recognize properties of graphs: A problem,SIG ACT News,5 (4) (1973), 15–16.
P. A. Smith, Fixed point theorems for periodic transformations,Amer. J. of Math.,63 (1941), 1–8.
A. Yao, Monotone Bipartite Graph Properties Are Evasive,SIAM J. on Computing,17 (1986), 517–520.