A generalized model for understanding evasiveness

DOI10.1016/0020-0190(89)90214-7MaRDI QIDQ1825645zbMATH OpenOpenAlexFDO

Authors Alok Aggarwal, Don Coppersmith, Daniel J. Kleitman

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90214-7

zbMATH Keywords

evasivenessgraph properties

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• Searching for an edge in a graph
• A topological approach to evasiveness
• The smallest nonevasive graph property
• An asymptotic bound for the complexity of monotone graph properties
• Evasiveness of subgraph containment and related properties

Cites work

• On recognizing graph properties from adjacency matrices

Cited in

(10)

• scientific article; zbMATH DE number 1688357 (Why is no real title available?)
• scientific article; zbMATH DE number 3902707 (Why is no real title available?)
• Monotone Bipartite Graph Properties are Evasive
• Graph properties in node-query setting: effect of breaking symmetry
• The smallest nonevasive graph property
• scientific article; zbMATH DE number 4003527 (Why is no real title available?)
• Searching for an edge in a graph
• Connectivity vs. reachability
• A lower bound for the recognition of digraph properties
• Reconstructing graphs from cut-set sizes

This page was built for publication: A generalized model for understanding evasiveness

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