Fixed-parameter complexity in AI and nonmonotonic reasoning.
Many relevant intractable problems become tractable if some problem parameter is fixed. However, various problems exhibit very different computational properties, depending on how the runtime required for solving them is related to the fixed parameter chosen. The theory of parameterized complexity deals with such issues, and provides general techniques for identifying fixed-parameter tractable and fixed-parameter intractable problems. We study the parameterized complexity of various problems in AI and nonmonotonic reasoning. We show that a number of relevant parameterized problems in these areas are fixed-parameter tractable. Among these problems are constraint satisfaction problems with bounded treewidth and fixed domain, restricted forms of conjunctive database queries, restricted satisfiability problems, propositional logic programming under the stable model semantics where the parameter is the dimension of a feedback vertex set of the program's dependency graph, and circumscriptive inference from a positive k-CNF restricted to models of bounded size. We also show that circumscriptive inference from a general propositional theory, when the attention is restricted to models of bounded size, is fixed-parameter intractable and is actually complete for a novel fixed-parameter complexity class.
Introduction
Many hard decision or computation problems are known to become tractable if a problem parameter is fixed
or bounded by a fixed value. For example the well-known NP-hard problems of checking whether a graph has
a vertex cover of size at most k, and of computing such a vertex cover if so, become tractable if the integer
k is a fixed constant, rather than being part of the problem instance. Similarly, the NP complete problem
of finding a clique of size k in a graph becomes tractable for every fixed k. Note, however, that there is an
important difference between these problems:
- The vertex cover problem is solvable in linear time for every fixed constant k. Thus the problem is not
only polynomially solvable for each fixed k, but, moreover, in time bounded by a polynomial p k whose
degree does not depend on k.
- The best known algorithms for finding a clique of size k in a graph are all exponential in k (typically, they
require runtime
n\Omega (k=2) ). Thus, for fixed k, the problem is solvable in time bounded by a polynomial p k ,
whose degree depends crucially on k.
Problems of the first type are called fixed-parameter tractable (fp-tractable), while problems of the second
type can be classified as fixed-parameter intractable (fp-intractable) [8]. It is clear that fixed-parameter
tractability is a highly desirable feature.
The theory of parameterized complexity, mainly developed by Downey and Fellows [8, 6, 5], deals with
general techniques for proving that certain problems are fp-tractable, and with the classification of fp-intractable
problems into a hierarchy of fixed-parameter complexity classes.
In this paper we study the fixed-parameter complexity of a number of relevant AI and NMR problems. In
particular, we show that the following problems are all fixed-parameter tractable (the parameters to be fixed
are added in square brackets after the problem description):
Constraint Satisfiability and computation of the solution to a constraint satisfaction problem (CSP) [fixed
parameters: (cardinality of) domain and treewidth of constraint scopes].
- Satisfiability of CNF [fixed parameter: treewidth of variable connection graph].
Prime Implicants of a q-CNF [fixed parameters: maximal number q of literals per clause and size of the
prime implicants to be computed].
Propositional logic programming [fixed parameter: size of a minimal feedback vertex set of the atom
dependency
Circumscriptive inference from a positive q-CNF [fixed parameters: maximal number q of literals per
clause and size of the models to be considered].
We believe that these results are useful both for a better understanding of the computational nature of the
above problems and for the development of smart parameterized algorithms for the solution of these and
related problems.
We also study the complexity of circumscriptive inference from a general propositional theory when the
attention is restricted to models of size k. This problem, referred-to as small model circumscription (SMC), is
easily seen to be fixed-parameter intractable, but it does not seem to be complete for any of the fp-complexity
classes defined by Downey and Fellows. We introduce the new class \Sigma 2 W [SAT ] as a miniaturized version of
the class \Sigma P
2 of the polynomial hierarchy, and prove that SMC is complete for \Sigma 2 W [SAT ]. This seems to be
natural, given that the nonparameterized problem corresponding to SMC is \Sigma P
-complete [9]. Note, however,
that completeness results for parameterized classes are more difficult to obtain. In fact, for obtaining our
completeness result we had to resort to the general version of circumscription (called P;Z-circumscription)
where the propositional letters of the theory to be circumscribed are partitioned into two subsets P and Z, and
only the atoms in P are minimized, while those in Z can float. The restricted problem, where P consists of
all atoms and Z is empty does not seem to be complete for \Sigma 2 W [SAT ], even though its non-parameterized
version is still \Sigma P
The paper is organized as follows. In Section 2 we state the relevant formal definitions related to fixed
parameter complexity. In Section 3 we deal with constraint satisfaction problems. In Section 4 we study fp-
tractable satisfiability problems. In Section 5 we deal with logic programming. Finally, in Section 6 we study
the problem of circumscriptive inference with small models.
Parameterized Complexity
Parameterized complexity [8] deals with parameterized problems, i.e., problems with an associated parameter.
Any instance S of a parameterized problem P can be regarded as consisting of two parts: the "regular"
instance I S , which is usually the input instance of the classical - non parameterized - version of P ; and the
associated parameter kS , usually of integer type.
Definition 1. A parameterized problem P is fixed-parameter tractable if there is an algorithm that correctly
decides, for input S, whether S is a yes instance of P in time f(kS )O(n c ), where n is the size of I S (jI
n), kS is the parameter, c is a constant, and f is an arbitrary function.
A notion of problem reduction proper to the theory of parameterized complexity has been defined.
Definition 2. A parameterized problem P fp-reduces to a parameterized problem P 0 by an fp-reduction if
there exist two functions f; f 0 and a constant c such that we can associate to any instance S of P an instance
satisfying the following conditions: (i) the parameter kS 0 of S 0 is f(kS ); (ii) the regular instance I S 0
is computable from S in time is a yes instance of P if and only if S 0 is a yes instance of
A parameterized class of problems C is a (possibly infinite) set of parameterized problems. A problem P
is C-complete if P 2 C and every problem P 0 2 C is fp-reducible to P .
A hierarchy of fp-intractable classes, called W -hierarchy, has been defined to properly characterize the
degree of fp-intractability associated to different parameterized problems. The relationship among the classes
of problems belonging to the W -hierarchy is given by the following chain of inclusions:
where, for each natural number t ? 0, the definition of the class W [t] is based on the degree t of the
complexity of a suitable family of Boolean circuits.
The most prominent W [1]-complete problem is the parameterized version of clique, where the parameter
is the clique size. W [1] can be characterized as the class of parameterized problems that fp-reduce to parameterized
CLIQUE. Similarly, W [2] can be characterized as the class of parameterized problems that fp-reduce
to parameterized Hitting Set, where the parameter is the size of the hitting set.
A k-truth value assignment for a formula E is a truth value assignment which assigns true to exactly k
propositional variables of E. Consider the following problem Parameterized SAT:
Instance: A Boolean formula E.
Parameter: k.
Question: Does there exist a k-truth value assignment satisfying E?
is the class of parameterized problems that fp-reduce to parameterized SAT. W [SAT ] is contained
in W [P ], where Boolean circuits are used instead of formulae. It is not known whether any of the
above inclusionships is proper or not, however the difference of all classes is conjectured.
The AW -hierarchy has been defined in order to deal with some problems that do not fit the W -classes [8].
The AW -hierarchy represents in a sense the parameterized counterpart of PSPACE in the classical complexity
setting. In this paper we are mainly interested in the class AW [SAT ]. Consider the following problem
Parameterized QBFSAT:
Instance: A quantified boolean formula
Question: Is \Phi valid? (Here, 9 k i x denotes the choice of some k i -truth value assignment for the variables
x, and 8 k j x denotes all choices of k j -truth value assignments for the variables x.)
is the class of parameterized problems that fp-reduce to parameterized QBFSAT.
3 Constraint Satisfaction Problems, Bounded Treewidth, and FP-Tractability
In this section we prove that Constraint Satisfaction Problems of bounded treewidth over a fixed domain are
FP tractable. In order to get this results we need a number of definitions. In Section 3.1 we give a very general
definition of CSPs; in Section 3.2 we define the treewidth of CSP problems and quote some recent results; in
Section 3.3 we show the main tractability result.
3.1 Definition of CSPs
An instance of a constraint satisfaction problem (CSP) (also constraint network) is a triple I = (V ar; U; C),
ar is a finite set of variables, U is a finite domain of values, and is a finite
set of constraints. Each constraint C i is a pair (S list of variables of length m i called
the constraint scope, and r i is an m i -ary relation over U , called the constraint relation. (The tuples of r i
indicate the allowed combinations of simultaneous values for the variables S i ). A solution to a CSP instance
is a substitution ar \Gamma! U , such that for each 1 . The problem of deciding whether a
CSP instance has any solution is called constraint satisfiability (CS). (This definition is taken almost verbatim
from [16].)
To any CSP instance I = (V ar; U; C), we associate a hypergraph
denotes the set of variables in the scope S of the constraint
C.
be the constraint hypergraph of a CSP instance I . The primal graph of I is a graph
E), having the same set of variables (vertices) as H(I) and an edge connecting any pair of
variables X;Y 2 V such that fX; Y g ' h for some h 2 H .
3.2 Treewidth of CSPs
The treewidth of a graph is a measure of the degree of cyclicity of a graph.
Definition 3 ([19]). A tree decomposition of a graph E) is a
tree, and - is a labeling function associating to each vertex p 2 N a set of vertices -(p) ' V , such that the
following conditions are satisfied:
1. for each vertex b of G, there is a p 2 N such that b 2 -(p);
2. for each edge fb; dg 2 F , there is a p 2 N such that fb; dg ' -(p);
3. for each vertex b of G, the set fp 2 N j b 2 -(p)g induces a (connected) subtree of T .
The width of the tree decomposition is \Gamma1. The treewidth of G is the minimum width
over all its tree decompositions.
Bodlaender [2] has shown that, for each fixed k, there is a linear time algorithm for checking whether a
graph G has treewidth bounded by k and, if so, computing a tree decomposition of G having width k at most.
Thus, the problem of computing a tree decomposition of a graph of width k is fp-tractable in the parameter
k.
The treewidth of a CSP instance I is the treewidth of its primal graph G(I). Accordingly, a tree decomposition
of I is a tree decomposition of G(I).
3.3 FP-Tractable CSPs
Constraint Satisfaction is easily seen to be NP-complete. Moreover, the parameterized version, where the
parameter is the total size of all constraint scopes, is W [1]-complete, and thus not fp-tractable. This follows
from well-known results on conjunctive query evaluation [7, 18], which is equivalent to constraint satisfaction
(cf. [14]). Therefore, also bounded treewidth CSP is fp-intractable and W [1]-hard. Indeed, the CSPs having
total size of the constraint scopes - k form a subclass of the CSPs having treewidth - k. Note that, for each
fixed k, CSPs of width - k can be evaluated in time O(n k log n) [15].
In this section we show that, however, if as an additional parameter we fix the size of the domain U , then
bounded treewidth CSP is fixed parameter tractable.
It is worthwhile noting that the general CSP problem remains NP-complete even for constant domain U .
(See, e.g., the 3-SAT problem discussed below.)
Theorem 1. Constraint Satisfaction with parameters treewidth k and universe size
So is the problem of computing a solution of a CSP problem with parameters k and u.
Proof. (Sketch.) Let I = (V ar; U; C) be a CSP instance having treewidth k and jU We exhibit an fp-
transformation from I to an equivalent CSP instance I assume w.l.o.g. that no constraint
scope S in I contains multiple occurrences of variables. (In fact, such occurrences can be easily removed by
a simple preprocessing of the input instance.) Note that, from the bound k on the treewidth, it follows that
each constraint scope contains at most k variables, and thus the constraint relations have arity at most k.
-i be a k-width tree decomposition of G(I) such that jV j - cjG(I)j, for a fixed predetermined
constant c. (This is always possible because Bodlaender's algorithm runs in linear time.) For each
vertex I 0 has a constraint C the scope S is a list containing the variables
belonging to -(p), and r is the associated relation, computed as described below.
The relations associated to the constraints of I 0 are computed through the following two steps:
1. For each constraint C i.e., the jvar(S 0 )j-fold cartesian product
of the domain U with itself.
2. For each constraint any constraint of I 0 such that var(S) '
Such a constraint must exist by definition of tree decomposition of the primal graph G(I).
Modify r 0 as follows. r rg. (In database terms, r 0
is semijoin-reduced by r.)
It is not hard to see that the instance I 0 is equivalent to I , in that they have exactly the same set of solutions.
Note that the size of I 0 is - jU j k (cjG(I)j), and even computing I 0 from I is feasible in linear time. Thus the
reduction is actually an fp-reduction.
The resulting instance I 0 is an acyclic constraint satisfaction problem which is equivalent to an acyclic
conjunctive query over a fixed database [14]. Checking whether such a query has a nonempty result and, in
the positive case, computing a single tuple of the result, is feasible in linear time by Yannakakis' well-known
algorithm [23]. ut
Note that, since CSP is equivalent to conjunctive query evaluation, the above result immediately gives us
a corollary on the program complexity of conjunctive queries, i.e. the complexity of evaluating conjunctive
queries over a fixed database [22]. The following result complements some recent results on fixed-parameter
tractability of database problems by Papadimitriou and Yannakakis [18].
Corollary 1. The evaluation of Boolean conjunctive queries is fp-tractable w.r.t. the treewidth of the query
and the size of the database universe. Moreover, evaluating a nonboolean conjunctive query is fp-tractable
in the input and output size w.r.t. the treewidth of the query and the size of the database universe.
4 FP-Tractable Satisfiability Problems
4.1 Bounded-width CNF Formulae
As an application of our general result on FP tractable CSPs we show that a relevant satisfiability problem is
also FP tractable.
The graph G(F ) of a CNF formula F has as vertices the set of propositional variables occurring in F and
has an edge fx; yg iff the propositional variables x and y occur together in a clause of F . The treewidth of F
is defined to be the treewidth of the associated graph G(F ).
Theorem 2. CNF Satisfiability with parameter treewidth k is fp-tractable. So is the problem of computing a
model of a CNF formula with parameter k.
Proof. (Sketch.) We fp-transform a CNF formula F into a CSP instance I(F defined as
follows. V ar contains a variable X p for each propositional variable p occurring in F ;
each clause D of F , I(F ) contains a constraint (S; r) where the constraint scope S is the list containing
all variables X p such that p is a propositional variable occurring in p, and the constraint relation r ' U jDj
consists of all tuples corresponding to truth value assignments satisfying D.
It is obvious that every model of F correspond to a solution of I(F ) and vice versa. Thus, in particular, F
is satisfiable if and only if I(F ) is a positive CSP instance.
Since G(F ) is isomorphic to G(I(F )), both F and I(F ) have the same treewidth. Moreover, any CNF
formula F of treewidth k has clauses of cardinality at most k. Therefore, our reduction is feasible in time
and is thus an fp-reduction w.r.t. parameter k.
By this fp-reduction, fp-tractability of CNF-SAT with the treewidth parameter follows from the fp-tractability
of CSPs w.r.t. treewidth, as stated in Theorem 1. ut
4.2 CNF with Short Prime Implicants
The problem of finding the prime implicants of a CNF formula is relevant to a large number of different areas,
e.g., in diagnosis, knowledge compilation, and many other AI applications.
Clearly, the set of the prime implicants of a CNF formula F can be viewed as a compact representation
of the satisfying truth assignments for F . It is worthwhile noting that the restriction of Parameterized SAT
to CNF formulae is fp-intractable. More precisely, deciding whether a q-CNF formula F has a k-truth value
assignment is W [2]-complete [8]. (We recall that a k-truth value assignment assigns true to exactly k propositional
Nevertheless, we identified a very natural parameterized version of satisfiability which is fp-tractable. We
simply take as the parameter the length of the prime implicants of the Boolean formula.
Given a q-CNF formula F , the Short Prime Implicants problem (SPI) is the problem of computing the
prime implicants of F having length - k, with parameters k and q.
Theorem 3. SPI is fixed-parameter tractable.
Proof. (Sketch.) Let F be a q-CNF formula. W.l.o.g., assume that F does not contain tautological clauses. We
generate a set IM k of implicants of F from which it is possible to compute the set of all prime implicants
of F having length - k. (this is very similar to the well-known procedure of generating vertex covers of
bounded size, cf. [4, 8]). Pick an arbitrary clause C of F . Clearly, each implicant I of F must contain at least
one literal of C. We construct an edge-labeled tree t whose vertices are clauses in F as follows. The root of
t is C. Each nonleaf vertex D has an edge labeled ' to a descendant, for each literal ' 2 D. As child attach
to this edge any clause E of F which does not intersect the set of all edge-labels from the root to the current
position. A branch is closed if such a set does not exist or the length of the path is k.
For each root-leaf branch fi of the tree, let I(fi) be the set containing the - k literals labeling the edges of
fi. Check whether I(fi) is a consistent implicant of F and add I(fi) to the set IM k
It is easy to see that the size of the tree t is bounded by q k and that for every prime implicant S of F having
length - k, S ' I holds, for some implicant I 2 IM k
Moreover, note that there are at most q k implicants in IM k For each implicant I 2 IM k the set of
all consistent prime implicants of F included in I can be easily obtained in time O(2 k jF j) from I . It follows
that SPI is fp-tractable w.r.t. parameters q and k. ut
5 Logic Programs with Negation
Logic programming with negation under the stable model semantics [13] is a well-studied form of nonmonotonic
reasoning.
A literal L is either an atom A (called positive) or a negated atom :A (called negative). Literals A and
:A are complementary; for any literal L, we denote by ::L its complementary literal, and for any set Lit of
literals,
A normal clause is a rule of the form
A
where A is an atom and each L i is a literal. A normal logic program is a finite set of normal clauses.
A normal logic program P is stratified [1], if there is an assignment str(\Delta) of integers 0,1,. to the predicates
in P , such that for each clause r in P the following holds: If p is the predicate in the head of r and
q the predicate in an L i from the body, then str(p) - str(q) if L i is positive, and str(p) ? str(q) if L i is
negative.
The reduct of a normal logic program P by a Herbrand interpretation I [13], denoted P I , is obtained from
P as follows: first remove every clause r with a negative literal L in the body such that ::L 2 I , and then
remove all negative literals from the remaining rules.
An interpretation I of a normal logic program P is a stable model of P [13], if I is the least Herbrand
model of P I .
In general, a normal logic program P may have zero, one, or multiple (even exponentially many) stable
models. Denote by stabmods(P ) the set of stable models of P .
It is well-known that every stratified logic program has a unique stable model which can be computed in
linear time.
The following problems are the main decision and search problems in the context of logic programming.
Main logic programming problems. Let P be a logic program.
1. Consistency: Determine whether P admits a stable model.
2. Brave Reasoning: Check whether a given literal is true in a stable model of P .
3. Cautious Reasoning: Check whether a literal is true in every stable model of P .
4. SM Computation: Compute an arbitrary stable model of P .
5. SM Enumeration: Compute the set of all stable models of P .
For a normal logic program P , the dependency graph G(P ) is a labeled directed graph (V;
the set of atoms occurring in P and A is a set of edges such that (p; q) 2 A is there exists a rule r 2 P having
p in its head and q in its body. Moreover, if q appears negatively in the body, then the edge (p; q) is labeled
with the symbol :. The undirected dependency graph G   (P ) of P is the undirected version of G(P ).
A feedback vertex set S of an undirected (directed) graph G is a subset X of the vertices of G such that
any cycle (directed cycle) contains at least one vertex in S. Clearly, if a feedback vertex set is removed from
G, then the resulting graph is acyclic. The feedback width of G is the minimum size over its feedback vertex
sets.
It was shown by Downey and Fellows [8, 4] that determining whether an undirected graph has feedback
width k and, in the positive case, finding a feedback vertex set of size k, is fp-tractable w.r.t. the parameter k.
Let P be a logic program defined over a set U of propositional atoms. A partial truth value assignment
(p.t.a.) for P is a truth value assignment to a subset U 0 of U . If - is a p.t.a. for P , denote by P [- ] the program
obtained from P as follows:
- eliminate all rules whose body contains a literal contradicting - ;
- eliminate from every rule body all literals whose literals are made true by - .
The following lemma is easy to verify.
Lemma 1. Let M be a stable model of some logic program P , and let - be a p.t.a. consistent with M . Then
M is a stable model of P [- ].
Theorem 4. The logic programming problems (1-5) listed above are all fp-tractable w.r.t. the feedback width
of the dependency graph of the logic program.
Proof. (Sketch.) Given a logic program P whose graph G   (P ) has feedback width k, compute in linear time
(see [8]) a feedback vertex set S for G   (P ) s.t.
Consider the set T of all the 2 k partial truth value assignments to the atoms in S.
For each p.t.a. - 2 T , P [- ] is a stratified program whose unique stable model M - can be computed in
linear time. For each
denotes the set of all stable models of P (this latter can be done in linear time, too, if suitable data structures
are used).
By definition of \Sigma , it suffices to note that every stable model M for
P belongs to \Sigma . Indeed, let - be the p.t.a. on S determined by M . By Lemma 1, it follows that M is a stable
model of P [- ] and hence M 2 \Sigma .
Thus, P has at most 2 k stable models whose computation is fp-tractable and actually feasible in linear time.
Therefore, the problem 5 above (Stable Model Enumeration) is fp-tractable. The fp-tractability of all other
problems follows. ut
It appears that an overwhelmingly large number of "natural" logic programs have very low feedback width,
thus the technique presented here seems to be very useful in practice. Note, however, that the technique does
not apply to some important and rather obvious cases. In fact, the method does not take care of the direction
and the labeling of the arcs in the dependency graph G(P ). Hence, positive programs width large feedback
width are not recognized to be tractable, although they are trivially tractable. The same applies, for instance,
for stratified programs having large feedback width, or to programs whose high feedback-with is exclusively
due to positive cycles.
Unfortunately, it is not known whether computing feedback vertex sets of size k is fixed-parameter tractable
for directed graphs [8].
Another observation leading to a possible improvement is the following. Call an atom p of a logic program
malignant if it lies on at least one simple cycle of G(P ) containing a marked (=negated) edge. Call an
atom benign if it is not malignant. It is easy to see that only malignant atoms can be responsible for a large
number of stable models. In particular, every stratified program contains only benign atoms and has exactly
one stable model. This suggest the following improved procedure:
- Identify the set of benign atoms occurring in P ;
- Drop these benign vertices from G   (P ), yielding H(P );
- Compute a feedback vertex set S of size - k of H(P );
- For each p.t.a. - over S compute the unique stable model M - of P [- ] and check whether this is actually
a stable model of P , and if so, output M - .
It is easy to see that the above procedure correctly computes the stable models of P . Unfortunately, as shown
by the next theorem, it is unlikely that this procedure can run in polynomial time.
Theorem 5. Determining whether an atom of a propositional logic program is benign is NP-complete.
Proof. (Sketch.) This follows by a rather simple reduction from the NP-complete problem of deciding
whether for two pairs of vertices of a directed graph G, there are two vertex-disjoint
paths linking x 1 to x 2 and y 1 to y 2 [11]. A detailed explanation will be given in the full paper. ut
We thus propose a related improvement, which is somewhat weaker, but tractable.
A atom p of a logic program P is called weakly malignant if it lies on at least one simple cycle of G   (P )
containing a marked (=negated) edge. An atom is called strongly benign if it is not weakly-malignant.
Lemma 2. Determining whether an atom of a propositional logic program is strongly benign or weakly
malignant can be done in polynomial time.
Proof. (Sketch.) It is sufficient to show that determining whether a vertex p of an undirected graph G with
Boolean edge labels lies on a simple cycle containing a marked edge. This can be solved by checking for each
marked edge hy 1 ; y 2 i of G and for each pair of neighbours x whether the graph G \Gamma fxg contains
two vertex-disjoint paths linking x 1 to y 1 and x 2 to y 2 , respectively. The latter is in polynomial time by a
result of Robertson and Seymour [20]. ut
We next present an improved algorithm for enumerating the stable models of a logic program P based on
the feedback width of a suitable undirected graph associated to P .
Modular Stable Model Enumeration procedure (MSME).
1. Compute the set C of the strongly connected components (s.c.c.) of G(P );
2. For each s.c.c. C 2 C, let PC be the set of rules of P that "define" atoms belonging to C, i.e., PC contains
any rule r 2 P whose head belongs to C;
3. Determine the set UC ' C of the strongly connected components (s.c.c.) of G(P ) whose corresponding
program PC is not stratified;
4. For each s.c.c. C 2 UC compute the set of strongly benign atoms SB(C) occurring in PC ;
5. Let P
6. Let H(P 0 ) be the the subgraph of G   (P 0 ) obtained by dropping every vertex p occurring in some set of
strongly benign atoms SB(C) for some C 2 UC;
7. Compute a feedback vertex set S of size - k of H(P 0 );
8. For each p.t.a. - over S compute the unique stable model M - of P [- ] and check whether this is actually
a stable model of P , and if so, output M - .
The feedback width of the graph H(P 0 ) is called the weak feedback-width of the dependency graph of P .
The following theorem follows from the fp-trectability of computing feedback vertex sets of size k for
undirected graph and from well-known modular computation methods for stable model semantics [10].
Theorem 6. The logic programming problems (1-5) listed above are all fp-tractable w.r.t. the weak feedback-
width of the dependency graph of the logic program.
Note that the methods used in this section can be adapted to show fixed-parameter tractability results for
extended versions of logic programming, such as disjunctive logic programming, and for other types of non-monotonic
reasoning. In the case of disjunctive logic programming, it is sufficient to extend the dependency
graph to contain a labeled directed edge between every pair of atoms occurring together in a rule head.
A different perspective to the computation of stable models has been recently considered in [21], where
the size of stable models is taken as the fixed parameter. It turns out that computing large stable models is
fixed-parameter tractable, whereas computing small stable models is fixed-parameter intractable.
6 The Small Model Circumscription Problem
In this section we study the fixed-parameter complexity of a tractable parametric variant of circumscription,
where the attention is restricted to models of small cardinality.
6.1 Definition of Small Model Circumscription
The Small Model Circumscription Problem (SMC) is defined as follows. Given a propositional theory T , over
a set of atoms given a propositional formula ' over vocabulary A, decide whether ' is
satisfied in a model M of T such that:
- M is of small size, i.e., at most k propositional atoms are true in M (written jM j - k); and
- M is P ; Z-minimal w.r.t. all other small models 1 , i.e., for each model M 0 of T such that jM 0 j - k,
1 In this paper, whenever we speak about P ; Z-minimality, we mean minimality as defined here.
This problem appears to be a miniaturization of the classical problem of (brave) reasoning with minimal
models. We believe that SMC is useful, since in many contexts, one has large theories, but is mainly interested
in small models (e.g. in abductive diagnosis).
Clearly, for each fixed k, SMC is tractable. In fact it sufficed to enumerate jAj k candidate interpretations in
an outer loop and for each such interpretation M check whether M
The latter can be done by an inner loop enumerating all small interpretations and performing some easy
checking tasks.
It is also not hard to see that SMC is fp-intractable. In fact the Hitting Set problem, which was shown to be
[2]-complete [8], can be fp-reduced to SMC and can be actually regarded as the restricted version of SMC
consists of a CNF having only positive literals. In Section 6.2 we present the
fp-tractable subclass of this version of SMC, where the maximum clause length in the theory is taken as an
additional parameter. However, in Section 6.3 we show that, as soon as the set Z of floating variables is not
empty, this problem becomes fp-intractable.
Since brave reasoning under minimal models was shown to be \Sigma P
2 complete in [9], and is thus one level
above the complexity of classical reasoning, it would be interesting to determine the precise fixed-parameter
complexity of the general version of SMC w.r.t. parameter k. This problem too is tackled in Section 6.3.
6.2 A Tractable Restriction of SMC
We restrict SMC by requiring that the theory T be a q-CNF with no negative literal occuring in it, and
by minimizing over all atoms occurring in the theory. The problem Restricted Small Model Circumscription
(RSMC) is thus defined as SMC except that T is required to be a purely positive q-CNF formula, the "floating"
set Z is empty, and the parameters are the maximum size k of the models to be considered, and the maximum
size q of the number of literals in the largest conjunct (=clause) of T .
Theorem 7. RSMC is fixed-parameter tractable.
Proof. (Sketch.) Since T is positive and ;, the set of minimal models of T to be considered are exactly
the prime implicants of T having size - k. By Theorem 3, computing these prime implicants for a q-CNF
theory is fp-tractable w.r.t. parameters k and q. Thus, the theorem easily follows. ut
6.3 The Fixed-Parameter Complexity of SMC
We first show that the slight modification of the fp-tractable problem RSMC where Z 6= ; is fp-intractable
and in fact W [SAT
The problem Positive Small Model Circumscription (PSMC) is defined as SMC except that T is required
to be a purely positive q-CNF formula, and the parameters are the maximum size k of the models to be
considered, and the maximum clause length q.
Let us define the Boolean formula count k (x), where x is a list of variables
1-i-n
iA
k-r-n
r
count k
Intuitively, in any satisfying truth value assignment for count k (x), the propositional variable q j
gets the value
true iff x i is the j th true variable among x Note that the size of count k (x) is O(kn 2 ).
The variables x in the formula above are called the external variables of the formula, while all the
other variables occurring in the formula are called private variables.
Whenever a theory T contains a count subformula, we assume w.l.o.g. that the private variables of this
subformula do not occur in T outside the subformula. In particular, if T contains two count subformulas,
then their set of private variables are disjoint.
Lemma 3. Let F be a formula and x a list of variables occurring in F . Then
only if there exists a truth value assignment oe for F assigning true to
exactly k variables from x.
Every k-truth value assignment oe satisfying F can be extended in a unique way to an assignment oe 0
satisfying F - count k (x).
Every satisfying truth value assignment for F - count k (x) assigns true to exactly k private variables of
count k (x) and true to exactly k variables from x.
Theorem 8. PSMC is W [SAT ]-hard. The problem remains hard even for 2-CNF theories.
Proof. (Sketch.) Let \Phi be a Boolean formula over propositional variables fx g. We fp-reduce the
W [SAT ]-complete problem of deciding whether there exists a k-truth value assignment satisfying \Phi to an
instance of PSMC where the maximum model size is 2k and the maximum clause length is 2.
be the private variables of the count k subformula.
Moreover, let T be the following 2-CNF positive theory:
We take g.
Note that a set M is a P ; Z minimal model of T having size - 2k
S is any subset of Z such that jM j - 2k.
From Lemma 3, every satisfying truth value assignment for \Phi 0 must make true exactly k variables from
variables from the set of private variables of count k . It follows that there exists a
minimal model M of T such that jM j - 2k only if there exists a k-truth value
assignment satisfying \Phi. ut
Let us now focus on the general SMC problem, where both arbitrary theories are considered and floating
variables are permitted. It does not appear that SMC is contained in W [SAT ]. On the other hand, it can
be seen that SMC is contained in AW [SAT ], but it does not seem to be hard (and thus complete) for this
class. In fact, AW [SAT ] is the miniaturization of PSPACE and not of \Sigma P
. No class corresponding to the
levels of the polynomial hierarchy have been defined so far in the theory of the fixed-parameter intractability.
reasoning problems, such as SMC, seem to require the definitions of such classes. We next
define the exact correspondent of \Sigma P
2 at the fixed-parameter level.
Definition of the class \Sigma 2 W [SAT ].
defined similarly to AW [SAT ], but the quantifier prefix is restricted to \Sigma 2 .
Parameterized QBF 2 SAT.
Instance: A quantified boolean formula 9 k1 x8 k2 yE.
Question: Is 9 k1 x8 k2 yE valid? (Here, 9 k1 x denotes the choice of some k 1 -truth value assignment for
the variables x, and 8 k2 y denotes all choices of k 2 -truth value assignments for the variables y.)
Definition 4. \Sigma 2 W [SAT ] is the set of all problems that fp-reduce to Parameterized QBF 2 SAT.
Membership of SMC in \Sigma 2 W [SAT ].
Let the problem Parameterized QBF 2 SAT- be the variant of Parameterized QBF 2 SAT where the quantifiers
9 k1 x and 8 k2 y are replaced by quantifiers 9 -k1 x and 8 -k2 y with the following meaning. 9 -k1 x ff
means that there exists a truth value assignment making at most k 1 propositional variables from x true such
that ff is valid. Simmetrically, 8 -k2 y ff means that ff is valid for every truth value assignment making at most
propositional variables from y true.
Lemma 4. Parameterized QBF 2 SAT- is in \Sigma 2 W [SAT ].
Proof. (Sketch.) It suffices to show that Parameterized QBF 2 SAT- is fp-reducible to Parameterized QBF 2 SAT.
be an instance of Parameterized
. It is easy to see that the following instance \Phi 0 of Parameterized QBF 2 SAT is equivalent to \Phi.
9
are new variables and E(x 1 - x 0
is obtained from E by substituting x
m). ut
Theorem 9. SMC is in \Sigma 2 W [SAT ].
Proof. (Sketch.) By Lemma 4 it is sufficient to show that every SMC instance S can be fp-reduced to an
equivalent instance \Phi(S) of Parameterized QBF 2 SAT- . Let be an SMC
instance, where
be two sets of fresh variables. \Phi(S) is defined as follows:
9 -k
where is obtained from T (P; Z) by substituting p 0
m).
The first part of \Phi(S) guesses a model M of T with at most k atoms among P [ Z which satisfies '. The
second part makes sure that the M is P ; Z minimal by checking that each model M 0 of T is either equivalent
to M over the P variables, or has at least one P variable true whereas the same variable is false in M . Hence
bravely entails ' under small models P ; Z circumscription if and only if \Phi(S) is valid. ut
]-hardness of SMC.
Theorem 10. SMC is \Sigma 2 W [SAT ]-hard, and thus \Sigma 2 W [SAT ]-complete.
Proof. (Sketch.) We show that Parameterized QBF 2 SAT is fp-reducible to SMC. Let \Phi be the following
instance of Parameterized QBF 2 SAT.
9 k1 x 1
We define a corresponding instance of SMC
w is a fresh variable, consists of
all the other variables occurring in T , namely, the variables in y and the private variables of the two count
subformulae.
We prove that \Phi is valid if and only if S(\Phi) is a yes instance of SMC.
(Only if part.) Assume \Phi is valid. Then, there exists a k 1 -truth value assignment oe to the variables x such
that for every k 2 -truth value assignment to the variables y, the formula E is satisfied.
Let M be an interpretation for T constructed as follows. M contains the k 1 variables from x which are
made true by oe and the first k 2 variables of y; in addition, M contains w and private variables which
make true the two count subformulae. This is possible by Lemma 3.
It is easy to see that M is a model for T . We now show that M is a P ; Z minimal model of T . Assume that
M 0 is a P ; Z smaller model. Due to the count k1 (x) subformula, M 0 must contain exactly k 1 atoms from x
and therefore M and M 0 coincide w.r.t. the x atoms. It follows that w 62 M 0 . However, by validity of \Phi and
the construction of M , M 0
(If part.) Assume there exists a P ; Z minimal model M of T such that M entails w and jM j - k. Note
that, by Lemma 3, it must hold that M contains exactly k 1 true variables from x and exactly k 2 true variables
from y.
Towards a contradiction, assume that \Phi is not valid. Then it must hold that for every k 1 -truth value assignment
oe to the variables x, there exists a k 2 -truth value assignment oe 0 to the variables y, such that oe [ oe 0
falsifies E. In particular, for the k 1 variables from x which are true according to M , it is possible to make
true exactly k 2 variables from y such that the formula E is not satisfied. Consider now the interpretation M 0
containing these true variables plus the true by the two count subformulae. M 0 is a
model of T whose P variables coincide with those of M except for w which belongs to M , but not to M 0 .
Therefore, M is not P ; Z minimal, a contradiction.
Finally, note that the transformation from \Phi to S(\Phi) is an fp-reduction. Indeed it is feasible in polynomial
time and is just linear in k. ut
Corollary 2. Parameterized QBF 2 SAT- is \Sigma 2 W [SAT ]-complete.
Proof. (Sketch.) Completeness follows from the fact that, as shown in Lemma 4, this problem belongs to
and by Theorem 10, which shows that the \Sigma 2 W [SAT ]-hard problem SMC is fp-reducible to
Parameterized QBF 2 SAT- . ut
Downey and Fellows [8] pointed out that completeness proofs for fixed parameter intractability classes
are generally more involved than classical intractability proofs. Note that this is also the case for the above
proof, where we had to deal with subtle counting issues. A straightforward downscaling of the standard \Sigma Pcompleteness proof for propositional circumscription appears not to be possible.
In particular, observe that we have obtained our completeness result for a very general version of propositional
minimal model reasoning, where there are variables to be minimized (P ) and floating variables (Z).
It is well-known that minimal model reasoning remains \Sigma P
complete even if all variables of a formula are
minimized (i.e., if Z is empty). This result does not seem to carry over to the setting of fixed parameter in-
tractability. Clearly, this problem, being a restricted version of SMC, is in \Sigma 2 W [SAT ]. Moreover it is easy
to see that the problem is hard for W [2] and thus fixed parameter intractable. However, we were not able to
show that the problem is complete for any class in the range from W [2] to \Sigma 2 W [SAT ], and leave this issue
as an open problem.
Open Problem. Determine the fixed-parameter complexity of SMC when all variables of the theory T are to
be minimized.



--R

Towards a Theory of Declarative Knowledge.
A linear-time algorithm for finding tree-decompositions of small treewidth
Optimal Implementation of Conjunctive Queries in relational Databases.
Fixed Parameter Tractability and Completeness.
Fixed Parameter Intractability (Extended Abstract).
Fixed Parameter Tractability and Completeness I: Basic Results.
On the Parametric Complexity of Relational Database Queries and a Sharper Characterization of W
Parameterized Complexity.
Propositional Circumscription and Extended Closed World Reasoning are
Disjunctive Datalog.
The Directed Subgraph Homeomorphism Problem.
Computers and Intractability.
The Stable Model Semantics for Logic Programming.
The Complexity of Acyclic Conjunctive Queries.
A Comparison of Structural CSP Decomposition Methods.
Closure Properties of Constraints.

On the Complexity of Database Queries.
Graph Minors II.
Graph Minors XX.
Computing Large and Small Stable Models.
Complexity of Relational Query Languages.
Algorithms for Acyclic Database Schemes.
--TR
A sufficient condition for backtrack-bounded search
A theory of diagnosis from first principles
Constraint satisfaction from a deductive viewpoint (Research Note)
Towards a theory of declarative knowledge
Tree clustering for constraint networks (research note)
Propositional circumscription and extended closed-world reasoning are MYAMPERSANDPgr;<supscrpt>p</supscrpt><subscrpt>2</subscrpt>-complete
Fixed-Parameter Tractability and Completeness I
A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
Closure properties of constraints
On the complexity of database queries (extended abstract)
Conjunctive-query containment and constraint satisfaction
On the Desirability of Acyclic Database Schemes
Computing large and small stable models
The complexity of acyclic conjunctive queries
Graph Algorithms
Declarative problem-solving using the DLV system
Computers and Intractability
Propositional lower bounds
Smodels - An Implementation of the Stable Model and Well-Founded Semantics for Normal LP
Pushing Goal Derivation in DLP Computations
Stable Model Semantics of Weight Constraint Rules
Descriptive and Parameterized Complexity
A Comparison of Structural CSP Decomposition Methods
The complexity of relational query languages (Extended Abstract)

--CTR
Stefan Szeider, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, Journal of Computer and System Sciences, v.69 n.4, p.656-674, December 2004
Carsten Sinz, Visualizing SAT Instances and Runs of the DPLL Algorithm, Journal of Automated Reasoning, v.39 n.2, p.219-243, August    2007
Logic programming and knowledge representation-the A-prolog perspective, Artificial Intelligence, v.138 n.1-2, p.3-38, June 2002
stable models;parameterized complexity;circumscription;prime implicants;logic programming;constraint satisfaction;conjunctive queries;fixed-parameter tractability;nonmonotonic reasoning