License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.17
URN: urn:nbn:de:0030-drops-64329
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6432/
Balaji, Nikhil ;
Datta, Samir ;
Kulkarni, Raghav ;
Podder, Supartha
Graph Properties in Node-Query Setting: Effect of Breaking Symmetry
Abstract
The query complexity of graph properties is well-studied 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 black-box 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 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(n^{1/(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 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 Node-Query Setting: Effect of Breaking Symmetry}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {17:1--17:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-016-3},
ISSN = {1868-8969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6432},
URN = {urn:nbn:de:0030-drops-64329},
doi = {10.4230/LIPIcs.MFCS.2016.17},
annote = {Keywords: query complexity, graph properties, symmetry and computation, forbidden subgraph}
}
|
Keywords: |
|
query complexity, graph properties, symmetry and computation, forbidden subgraph |
|
Collection: |
|
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
19.08.2016 |
