Constraint satisfaction problems in clausal form: Autarkies and minimal unsatisfiability.
Oliver Kullmann · 2007
We consider the problem of generalising boolean formulas in conjunctive normal form by allowing non-boolean variables, where our goal is to maintain combinatorial properties. Requiring that a literal involves only a single variable, the most general form of literals is given by the well-known “signed literals”, however we will argue that only the most restricted form of generalised clause-sets, corresponding to “sets of no-goods” in the AI literature, maintains the essential properties of boolean conjunctive normal forms. We start our investigations by building up a solid foundation for (generalised) clause-sets, including the notion of autarky systems, the interplay between autarkies and resolution, and basic notions of (DP-)reductions. As a basic combinatorial parameter of generalised clause-sets, we introduce the (generalised) notion of deficiency, which in the boolean case is the difference between the number of clauses and the number of variables. We obtain fixed parameter tractability (FPT) of satisfiability decision for generalised clause-sets, using as parameter the maximal deficiency (over all sub-clause-sets). Another central result in the boolean case regarding the deficiency is the classification of minimally unsatisfiable clause-sets with low deficiency (MU(1), MU(2), ...). We generalise the well-known characterisations of boolean MU(1). The proofs for FPT and MU(1) are not straight-forward, but are obtained by an interplay between suitable generalisations of techniques and notions from the boolean case, and exploiting combinatorial properties of the natural translation of (generalised) clause-sets into boolean clause-sets. Of fundamental importance here is autarky theory, and we concentrate especially on matching autarkies (based on matching theory). A natural question considered here is to determine the structure of (matching) lean clause-sets, which do not admit non-trivial (matching) autarkies. Special lean clause-sets are minimally unsatisfiable (generalised) clause-sets, and we consider the generalisation to irredundant clause-sets, so that also satisfiable clause-sets can be taken into account, with a special emphasise on hitting clause-sets (which are irredundant in a very strong sense) and the generalisation to multihitting clause-sets. Supported by EPSRC Grant GR/S58393/01 1 Electronic Colloquium on Computational Complexity, Report No. 55 (2007)