M. Lackner, A. Pfandler:

"Fixed-Parameter Algorithms for Finding Minimal Models";

Talk: Logic and interactions 2012, CIRM, Marseille, France; 2012-01-30 - 2012-03-02.

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).

Created from the Publication Database of the Vienna University of Technology.