2015/10/28 by Nikhil Balaji, Samir Datta, Balaji, Nikhil +5 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1510.08267
26 pages, 8 figures
arxiv created 2015/10/28 · arxiv updated 2015/10/29
The query complexity of graph properties is well-studied when queries are on edges. We investigate the same when queries are on nodes. In this setting a graph G = (V, E) on n vertices and a property P are given. A black-box access to an unknown subset S ⊆ V is provided via queries of the form `Does i ∈ S?'. We are interested in the minimum number of queries needed in worst case in order to determine whether G[S], the subgraph of G induced on S, satisfies P. Apart from being combinatorially rich, this setting allows us to initiate a systematic study of breaking symmetry in the context of query complexity of graph properties. In particular, we focus on hereditary graph properties. The monotone functions in the node-query setting translate precisely to the hereditary graph properties. The famous Evasiveness Conjecture asserts that even with a minimal symmetry assumption on G, namely that of vertex-transitivity, the query complexity for any hereditary graph property in our setting is the worst possible, i.e., n. We show that in the absence of any symmetry on G it can fall as low as O(n1/(d + 1) ) where d denotes the minimum possible degree of a minimal forbidden sub-graph for P. In particular, every hereditary property benefits at least quadratically. The main question left open is: can it go exponentially low for some hereditary property? We show that the answer is no for any hereditary property with finitely many forbidden subgraphs by exhibiting a bound of Ω(n1/k) for some constant k depending only on the property. For general ones we rule out the possibility of the query complexity falling down to constant by showing Ω(log n/ log log n) bound. Interestingly, our lower bound proofs rely on the famous Sunflower Lemma due to Erdös and Rado.