2016/10/28 by Thomas Zeume, Zeume, Thomas
Computer Science · #68Q15 #68Q17 #68Q19 #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.LO #msc:68Q15 #msc:68Q17 #msc:68Q19
paper · pdf · doi:10.48550/arxiv.1610.09089
An extended abstract of this work appeared in the proceedings of the conference Mathematical Foundations of Computer Science 2014 (MFCS 2014)
arxiv created 2016/10/28 · openalex publication_date 2016/10/28 · arxiv updated 2016/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.