An ?(n 5/4) lower bound on the randomized complexity of graph properties

COMBINATORICAPublished 1 March 1991

Valerie King

DOI10.1007/bf01375470

Source URL

Citations15

SJR quartileQ1

SJR score1.27

SNIP1.58

TL;DR

Yao's lower bound on the randomized complexity of any nontrivial monotone graph property from Ω (n log1/12n) to Ω(n5/4) is improved.

Abstract

A decision tree algorithm determines whether an input graph withn nodes has a property by examining the entries of the graph's adjacency matrix and branching according to the information already gained. All graph properties which are monotone (not destroyed by the addition of edges) and nontrivial (holds for somes but not all graphs) have been shown to require Ω(n 2) queries in the worst case. In this paper, we investigate the power of randomness in recognizing these properties by considering randomized decision tree algorithms in which coins may be flipped to determine the next entry to be examined. The complexity of a randomized algorithm is the expected number of entries that are examined in the worst case. The randomized complexity of a property is the minimum complexity of any randomized decision tree algorithm which computes the property. We improve Yao's lower bound on the randomized complexity of any nontrivial monotone graph property from Ω(n log1/12 n) to Ω(n 5/4).

Keywords

Computer ScienceEngineering

Theoretical Computer ScienceOn recognizing graph properties from adjacency matrices

183 Citations1976Ronald L. Rivest, Jean Vuillemin

A non-constructive argument (not based on the construction of an “oracle”) settles this question for d a prime power: 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.

COMBINATORICAA topological approach to evasiveness

163 Citations1984Jeff Kahn, Michael Saks +1 more

The truth of Karp's conjecture is shown to follow from another conjecture concerning group actions on topological spaces and a special case of the conjecture is proved which is applied to prove Karp’s conjecture for the case of properties of graphs on a prime power number of vertices.

ACM SIGACT NewsOn the time required to recognize properties of graphs

82 Citations1973Arnold L. Rosenberg

In a recent paper [i], Holt and Reingold have proved the following results: any algorithm which, given an n-node graph, detects whether or not the graph enjoys property P must in the worst case probe 0(n 2) entries of the incidence matrix.

View PDF

Journal of Combinatorial Theory Series BFurther results on the Aanderaa-Rosenberg conjecture

45 Citations1980Daniel J. Kleitman, D J Kwiatkowski

It is shown that any nontrivial monotone graph property on n vertices is at least n 2 9 - evasive, and stronger results are obtained for values of n that are powers of primes less than 14.

Lower bounds on the complexity of graph properties

32 Citations1988Valerie King

In this simple model, a decision tree algorithm must determine whether an unknown digraph on nodes {1, 2, …, n} has a given property by asking questions of the form “Is edge in the graph?”, the complexity of a property is the number of questions which must be asked in the worst case.

Lower bounds to randomized algorithms for graph properties

30 Citations1987Andrew Chi-Chih Yao

Progress is reported on showing that Ω(n(log n)1/12) edges must be examined by a randomized algorithm for determining any nontrivial monotone graph property.