[Zurück]

M. Lackner, A. Pfandler:
"Fixed-Parameter Algorithms for Finding Minimal Models";
Vortrag: Logic and interactions 2012, CIRM, Marseille, France; 30.01.2012 - 02.03.2012.

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