Article ID Journal Published Year Pages File Type
4950572 Information and Computation 2017 14 Pages PDF
Abstract
In this work the dynamic descriptive complexity of the k-clique query is studied. It is shown that when edges may only be inserted then k-clique can be maintained by a quantifier-free update program of arity k−1, but it cannot be maintained by a quantifier-free update program of arity k−2 (even in the presence of unary auxiliary functions). This establishes an arity hierarchy for graph queries for quantifier-free update programs under insertions. The proof of the lower bound uses upper and lower bounds for Ramsey numbers.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,