scientific article; zbMATH DE number 168429

From MaRDI portal
Publication:4036171





Let \(C^ R(P)\) be the number of questions of the form `Does the graph \(G\) contain the edge \(e(i,j)\)?' that have to be asked in the worst case by any randomized decision tree algorithm for computing an \(n\)-vertex graph property \(P\). For non-trivial, monotone graph properties it is known that the deterministic complexity is \(\Omega(n^ 2)\) [see \textit{R. Rivest} and \textit{Vuillemin} , On recognizing graph properties from adjacency matrices, Theor. Comp. Sci. 3, 371-384 (1976; Zbl 0358.68079)]. The best uniform lower bound for all non-trivial, monotone graph properties is \(\Omega(n^{4/3})\) due to \textit{P. Hajnal} [Complexity of graph properties, An \(\Omega(n^{4/3})\) lower bound on the randomized complexity of graph properties. Combinatorica 11(2), 131-143 (1991; Zbl 0743.68076)]. No non-trivial, monotone graph property is known having a randomized complexity of less than \(n^ 2/4\). Some properties have been proven to have complexity of \(\Omega(n^ 2)\) [see \textit{A. Yao}, Probabilistic computation: towards a unified measure of complexity, Proc. 18th IEEE FOCS, 222-227 (1977)]. We refine the idea of Yao. This leads to a further improvement in the reductions of arbitrary graph properties to bipartite graph properties [see \textit{V. King}, Lower bounds on the complexity of graph properties, Proc. 20th ACM STOC, 468-476 (1988)] and yields a uniform lower bound for the subgraph isomorphism properties of \(\Omega(n^{3/2})\). Furthermore we show, that a large variety of isomorphism properties has as well as \(k\)-colourability require \(\Omega(n^ 2)\) questions.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036171)