AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

The model-checking problem of first-order properties over relational structures constitutes one of the largest natural classes of problems for which we have a fine-grained characterization of its hardness. In particular, consider a first-order property psi defined by k existential quantifiers followed by a universal one (Exists^k Forall), and a graph G on m edges. For the problem of model checking psi over G, Bringmann, Fischer and Künnemann [CCC 19'] gave a dichotomy: they either give a polynomial-time improvement over the O(m^k)-baseline algorithm, or show that it requires time m^{k - o(1)} assuming the MAX3SAT hypothesis.

In this work we consider a natural optimization variant: instead of asking for k vertices which make the predicate true for all vertices y, we ask for the k vertices which maximize or minimize the number of y's which satisfy the predicate. In the same spirit, we give a dichotomy characterizing the hardness of all such predicates. Moreover, we extend the results to a characterization of predicates that admit a constant factor approximation.

Karl Bringmann

--email hidden

passcode not visible

logged in users only