Balaji, Nikhil ;
Datta, Samir ;
Kulkarni, Raghav ;
Podder, Supartha
Graph Properties in NodeQuery Setting: Effect of Breaking Symmetry
Abstract
The query complexity of graph properties is wellstudied when queries are on the edges. We investigate the same when queries are on the nodes. In this setting a graph G = (V,E) on n vertices and a property P are given. A blackbox access to an unknown subset S of V is provided via queries of the form "Does i belong to S?". We are interested in the minimum number of queries needed in the worst case in order to determine whether G[S]  the subgraph of G induced on S  satisfies P.
Our primary motivation to study this model comes from the fact that it allows us to initiate a systematic study of breaking symmetry in the context of query complexity of graph properties. In particular, we focus on the hereditary graph properties  properties that are closed under deletion of vertices as well as edges. The famous Evasiveness Conjecture asserts that even with a minimal symmetry assumption on G, namely that of vertextransitivity, 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(n^{1/(d + 1)}) where d denotes the minimum possible degree of a minimal forbidden subgraph 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 Omega(n^{1/k}) for a 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 Omega(log(n)*log(log(n))) bound. Interestingly, our lower bound proofs rely on the famous Sunflower Lemma due to Erdos and Rado.
BibTeX  Entry
@InProceedings{balaji_et_al:LIPIcs:2016:6432,
author = {Nikhil Balaji and Samir Datta and Raghav Kulkarni and Supartha Podder},
title = {{Graph Properties in NodeQuery Setting: Effect of Breaking Symmetry}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {17:117:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6432},
URN = {urn:nbn:de:0030drops64329},
doi = {10.4230/LIPIcs.MFCS.2016.17},
annote = {Keywords: query complexity, graph properties, symmetry and computation, forbidden subgraph}
}
19.08.2016
Keywords: 

query complexity, graph properties, symmetry and computation, forbidden subgraph 
Seminar: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Issue date: 

2016 
Date of publication: 

19.08.2016 