Graph properties in node-query setting: effect of breaking symmetry

DOI10.4230/LIPICS.MFCS.2016.17MaRDI QIDQ4608576zbMATH OpenOpenAlexFDO

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

Publication date 21 March 2018

Full work available at URL https://arxiv.org/abs/1510.08267

zbMATH Keywords

symmetryquery complexityforbidden subgraphgraph properties

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Abstract: 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 $mathcalP$ are given. A black-box access to an unknown subset $SsubseteqV$ is provided via queries of the form `Does $iinS$?'. 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 $mathcalP$. 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(n^{1/(d+1)})$ where $d$ denotes the minimum possible degree of a minimal forbidden sub-graph for $mathcalP$. 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 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 $Omega(logn/loglogn)$ bound. Interestingly, our lower bound proofs rely on the famous Sunflower Lemma due to Erd"os and Rado.

Recommendations

• A generalized model for understanding evasiveness
• An asymptotic bound for the complexity of monotone graph properties
• Searching for an edge in a graph
• On the Query Complexity of Estimating the Distance to Hereditary Graph Properties

This page was built for publication: Graph properties in node-query setting: effect of breaking symmetry

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608576)