Aanderaa–Karp–Rosenberg conjecture
that have to be answered to determine whether or not an undirected graph has a particular property such as planarity or bipartiteness.
They are named after Stål Aanderaa, Richard M. Karp, and Arnold L. Rosenberg.
According to the conjecture, for a wide class of properties, no algorithm can guarantee that it will be able to skip any questions: any algorithm for determining whether the graph has the property, no matter how clever, might need to examine every pair of vertices before it can give its answer.
More precisely, the Aanderaa–Rosenberg conjecture states that any deterministic algorithm must test at least a constant fraction of all possible pairs of vertices, in the worst case, to determine any non-trivial monotone graph property.
If an edge is ever found in this way, break out of the loop, and report that the graph is non-empty, and if the loop completes without finding any edges, then report that the graph is empty.
The algorithm described above is not the only possible method of testing for non-emptiness, but the Aanderaa–Karp–Rosenberg conjecture implies that every deterministic algorithm for testing non-emptiness has the same worst-case query complexity,
For this property, the result is easy to prove directly: if an algorithm does not perform
Graphs are assumed to have an implicit representation in which each vertex has a unique identifier or label and in which it is possible to test the adjacency of any two vertices, but for which adjacency testing is the only allowed primitive operation.
that have to be read in the worst case by a deterministic algorithm that computes the function.
In the worst case, regardless of the order it chooses to examine its input, the first
If an algorithm doesn't read this bit, it might output an incorrect answer.
However, the randomized algorithm must still output the correct answer for all inputs: it is not allowed to make errors.
Randomized query complexity can be defined for both Las Vegas and Monte Carlo algorithms, but the randomized version of the Aanderaa–Karp–Rosenberg conjecture is about the Las Vegas query complexity of graph properties.
In the context of this conjecture, the function to be evaluated is the graph property, and the input can be thought of as a string of size
For deterministic algorithms, Rosenberg (1973) originally conjectured that for all nontrivial graph properties on
queries is the property of being a scorpion graph, first described in Best, van Emde Boas & Lenstra (1974).
queries are needed to test for any nontrivial monotone graph property.
[7] This conjecture says that the best algorithm for testing any nontrivial monotone property must (in the worst case) query all possible edges.
This conjecture is still open, although several special graph properties have shown to be evasive for all
[8] The conjecture has also been resolved for all non-trivial monotone properties on bipartite graphs.
[10] In Kahn, Saks & Sturtevant (1984) the conjecture was generalized to properties of other (non-graph) functions too, conjecturing that any non-trivial monotone function that is weakly symmetric is evasive.
queries are required for testing nontrivial monotone properties even if randomized algorithms are permitted.
) on all monotone properties follows from a very general relationship between randomized and deterministic query complexities.
The first superlinear lower bound for all monotone properties was given by Yao (1991) who showed that
Some recent results give lower bounds which are determined by the critical probability
Friedgut, Kahn & Wigderson (2002) showed that any monotone property with critical probability
[12] It is obtained by combining the randomized lower bound with the quantum adversary method.
, unlike the classical case, due to Grover's algorithm which gives an
lower bound, for example non-emptiness (which follows from the optimality of Grover's algorithm) and the property of containing a triangle.
queries,[13] and the monotone property of containing more than half the possible number of edges (also called the majority function) requires
