@inproceedings{52a7f99849604c68a3e9622d6961820d,

title = "Evasiveness of subgraph containment and related properties",

abstract = "We prove new results on evasiveness of monotone graph properties by extending the techniques of Kahn, Saks and Sturtevant [4]. For the property of containing a subgraph isomorphic to a fixed graph, and a fairly large class of related n-vertex graph properties, we show evasiveness for an arithmetic progression of values of n. This implies a ½n2 − O(n) lower bound on the decision tree complexity of these properties. We prove that properties that are preserved under taking graph minors are evasive for all sufficiently large n. This greatly generalizes the evasiveness result for planarity [1]. We prove a similar result for bipartite subgraph containment.",

keywords = "Decision tree complexity, Evasiveness, Graph property testing, Monotone graph properties",

author = "Amit Chakrabarti and Subhash Khot and Yaoyun Shi",

year = "2001",

doi = "10.1007/3-540-44693-1_10",

language = "English (US)",

isbn = "9783540416951",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "110--120",

editor = "Afonso Ferreira and Horst Reichel",

booktitle = "STACS 2001 - 18th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",

note = "18th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2001 ; Conference date: 15-02-2001 Through 17-02-2001",

}