Martin Lackner (Vienna University of Technology), Fixed-Parameter Algorithms for Finding Minimal Models (joint work with Andreas Pfandler).

Schedule

  • Feb. 3, 2012, 14:00 - 14:30

Abstract

Computing minimal models is an important task in AI and Reasoning that appears in formalisms such as circumscription, diagnosis and answer set programming. Deciding whether there is a minimal model containing a given variable is known to be Sigma2^P complete. In this talk I present a study of this problem from the viewpoint of parame- terized complexity theory that has been undertaken together with Andreas Pfan- dler. We performed an extensive complexity analysis of this problem with respect to eleven parameters. We identi ed tractable fragments based on combinations of these parameters by giving several xed-parameter algorithms. Furthermore, for the remaining combinations we showed parameterized hardness results and thus proved that no further xed-parameter algorithms exist for these parameters (under usual complexity theoretic assumptions). In particular, we proved W[2]- completeness when parameterizing by the maximum cardinality of the model. This answered an open question posed in (Gottlob, Scarcello, and Sideri 2002).