License
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://drops.dagstuhl.de/opus/volltexte/2016/6432/
Go to the corresponding LIPIcs Volume Portal


Balaji, Nikhil ; Datta, Samir ; Kulkarni, Raghav ; Podder, Supartha

Graph Properties in Node-Query Setting: Effect of Breaking Symmetry

pdf-format:
LIPIcs-MFCS-2016-17.pdf (0.5 MB)


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
Seminar: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI