Publisher Summary The past few years have seen enormous progress in the performance of
Boolean satisfiability (SAT) solvers. Despite the worst-case exponential run time of all known …

Handbook of Knowledge Representation describes the essential foundations of Knowledge
Representation, which lies at the core of Artificial Intelligence (AI). The book provides an up …

The existence of a polynomial kernel for Odd Cycle Transversal was a notorious open
problem in parameterized complexity. Recently, this was settled by the present authors …

A backdoor set is a set of variables of a propositional formula such that fixing the truth values
of the variables in the backdoor set moves the formula into some polynomial-time decidable …

We continue the development of matroid-based techniques for kernelization, initiated by the
present authors [47]. We significantly extend the usefulness of matroid theory in …

Parameterized complexity is a new theoretical framework that considers, in addition to the
overall input size, the effects on computational complexity of a secondary measurement, the …

We develop a novel framework, the implicit hitting set approach, for solving a class of
combinatorial optimization problems. The explicit hitting set problem is as follows: given a …

The search of a precise measure of what hardness of SAT instances means for state-of-the-
art solvers is a relevant research question. Among others, the space complexity of treelike …

Abstract Answer Set Programming (ASP) is an increasingly popular framework for
declarative programming that admits the description of problems by means of rules and …

In this paper we extend the classical notion of strong and weak backdoor sets for SAT and
CSP by allowing that different instantiations of the backdoor variables result in instances that …