[Back]

M. Lackner, A. Pfandler:
"Fixed-Parameter Algorithms for Finding Minimal Models";
Talk: Universität Siegen, Siegen, Deutschland; 03-22-2012.

Computing subset-minimal models of propositional formulas is an important task in AI 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 $\Sigma_2^P$-complete. A successful way of dealing with intractability is the concept of parameterized complexity theory, where parameters and their influence on the complexity of the problem are studied. In this talk I present a study of this problem from the viewpoint of parameterized complexity theory that has been undertaken together with Martin Lackner. We performed an extensive complexity analysis of this problem considering various natural parameters. We identified tractable fragments based on combinations of these parameters by giving several fixed-parameter algorithms and proved that no further fixed-parameter algorithms exist (under usual complexity-theoretic assumptions).