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