[Back]

J. Dreier, P. Rossmanith:
"Approximate Evaluation of First-Order Counting Queries";
Talk: ACM-SIAM Symposium on Discrete Algorithms (SODA), Alexandria, Virginia, U.S.; 2021-01-10 - 2021-01-13; in: "Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms", (2021), ISBN: 978-1-61197-646-5; 1 - 20.

Kuske and Schweikardt introduced the very expressive rstorder
counting logic FOC(P) to model database queries with
counting operations. They showed that there is an e cient
model-checking algorithm on graphs with bounded degree,
while Grohe and Schweikardt showed that probably no such
algorithm exists for trees of bounded depth. We analyze
the fragment FO(f>0g) of this logic. While we remove
for example subtraction and comparison between two nonatomic
counting terms, this logic remains quite expressive:
We allow nested counting and comparison between counting
terms and arbitrarily large numbers. Our main result is
an approximation scheme of the model-checking problem for
FO(f>0g) that runs in linear fpt time on structures with
bounded expansion. This scheme either gives the correct
answer or says \I do not know." The latter answer may
only be given if small perturbations in the number-symbols
of the formula could make it both satis ed and unsatis ed.
This is complemented by showing that exactly solving the
model-checking problem for FO(f>0g) is already hard on
trees of bounded depth and just slightly increasing the
expressiveness of FO(f>0g) makes even approximation hard
on trees.

http://dx.doi.org/10.1137/1.9781611976465.104

https://publik.tuwien.ac.at/files/publik_299562.pdf