{"ID":23012312,"CreatedAt":"2026-09-17T04:38:43.538340206Z","UpdatedAt":"2026-09-17T04:38:43.538340206Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.18875","arxiv_id":"2609.18875","title":"Counting on Nowhere Dense Classes","abstract":"For every effectively nowhere dense class $\\mathcal{C}$ of relational structures, we present an algorithm that runs an almost-linear-time preprocessing step on a given structure $\\mathcal{A} \\in \\mathcal{C}$ and a first-order formula $φ(x_1, \\dots, x_k, y_1, \\dots, y_\\ell)$. After the preprocessing, whenever given a tuple $\\bar{v} \\in A^k$, the algorithm computes the number of tuples $\\bar{w} \\in A^\\ell$ that satisfy $\\mathcal{A} \\models φ(\\bar{v}, \\bar{w})$ in constant time. Building on this, we provide an algorithm for constant-time query answering and constant-delay enumeration after almost-linear-time preprocessing for the recently introduced logic clique-guarded first-order logic with counting (cgFOC) on effectively nowhere dense classes. This generalises the testing and enumeration results for first-order logic [Schweikardt, Segoufin, and Vigny, JACM 2022] and the evaluation result for the first-order logic with counting FOC1 [Grohe and Schweikardt, PODS 2018] on nowhere dense classes.","short_abstract":"For every effectively nowhere dense class $\\mathcal{C}$ of relational structures, we present an algorithm that runs an almost-linear-time preprocessing step on a given structure $\\mathcal{A} \\in \\mathcal{C}$ and a first-order formula $φ(x_1, \\dots, x_k, y_1, \\dots, y_\\ell)$. After the preprocessing, whenever given a tu...","url_abs":"https://arxiv.org/abs/2609.18875","url_pdf":"https://arxiv.org/pdf/2609.18875v1","authors":"[\"Steffen van Bergerem\",\"Nicole Schweikardt\"]","published":"2026-09-16T16:11:26Z","proceeding":"cs.LO","tasks":"[\"cs.LO\"]","methods":"[]","has_code":false}