Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Fine-Grained Complexity of Exists^k-Forall-Quantified First-Order Graph Properties: Optimization and Approximability (Master Thesis)
Speaker:Alejandro Cassis
coming from:Fachrichtung Informatik - Saarbrücken
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 25 February 2020
Duration:30 Minutes
Building:E1 4
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.

Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Karl Bringmann, 02/04/2020 05:03 PM
  • Karl Bringmann, 02/04/2020 05:03 PM -- Created document.