Name
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 $\mathcal{P}$ are given. A black-box access to an unknown subset $S \subseteq V$ is provided via queries of the form `Does $i \in S$?'. 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 $\mathcal{P}$. 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 $\mathcal{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 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(\log n/ \log \log n)$ bound. Interestingly, our lower bound proofs rely on the famous Sunflower Lemma due to Erd\"os and Rado. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.4230/LIPIcs.MFCS.2016.17 | mathematical foundations of computer science |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Forbidden graph characterization,Graph power,Hereditary property,Cycle graph,Null graph,Degree (graph theory),Factor-critical graph,Mathematics,Complement graph | Journal | abs/1510.08267 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikhil Balaji | 1 | 9 | 4.24 |
| Samir Datta | 2 | 200 | 19.82 |
| Raghav Kulkarni | 3 | 172 | 19.48 |
| Supartha Podder | 4 | 1 | 1.02 |