A generalized model for understanding evasiveness
type: Item
instance of: scholarly article
title: A generalized model for understanding evasiveness
zbMATH Open document ID: 0684.68044
DOI: 10.1016/0020-0190(89)90214-7
author: Alok Aggarwal
author: Don Coppersmith
author: Daniel J. Kleitman
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: In the study of evasive graph properties one considers decision-tree like algorithms which decide graph properties by probing for the resence or absence of particular edges in an initially fully unknown graph. The algorithms are adaptive in the sense that the answers on previous questions influence the choice of the next edge to be probed. The algorithm terminates as soon as the property under investigation can be decided on the basis of the partial information about the graph selected so far. Evasive properties are those properties where the algorithm can be forced to probe all edges before it can decide the property. It is known that a large collection of monotone non-trivial graph properties are evasive, and that all such properties force the algorithm to probe at least one quarter of all edges. The class of possible questions has been enlarged: given a set of vertices the number of edges between vertices in this set is provided. On the other hand the aim of the algorithm has become the determination of the complete graph - a target which in the single-edge probe model immediately would force evasiveness. The authors show that, given the new type of questions arbitrary graphs (and consequently all graph properties) can be deciced in \((2n^ 2/\log n)+o(n^ 2/\log n)\) questions and that this number is optimal up to a constant factor. This result is obtained from a similar result (an O(n/log n) bound) for a one-dimensional version of the problem, which in turn is used as a key lemma in the proof of the two-dimensional result. Only in the final section the case of deciding graph properties with use of the new sort of questions is addressed. A connection with a communication complexity result by Hajnal, Mass and Turan is presented.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4121421
zbMATH Keywords: evasiveness
zbMATH Keywords: graph properties
reviewed by: Peter van Emde Boas
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90214-7
OpenAlex ID: W2042143555
cites work: On recognizing graph properties from adjacency matrices
description: scientific article; zbMATH DE number 4121421