2026-07-23T03:22:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6432 2024-03-06T10:38:15Z ddc:004 open_access

Graph Properties in Node-Query Setting: Effect of Breaking Symmetry Balaji, Nikhil Datta, Samir Kulkarni, Raghav Podder, Supartha query complexity graph properties symmetry and computation forbidden subgraph 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikhil Balaji and Samir Datta and Raghav Kulkarni and Supartha Podder 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.17 urn:nbn:de:0030-drops-64329 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.17 eng https://creativecommons.org/licenses/by/3.0/legalcode