Skip to main content

Parameterized Complexity of Weighted Satisfiability Problems

Heribert Vollmer ( University of Hannover, Germany )

We consider the weighted satisfiability problem for Boolean circuits and propositional formulae, where the weight of an assignment is the number of variables set to true. We study the parameterized complexity of these problems and related counting problems and initiate a systematic study of the complexity of its fragments. "Systematic" here means that the fragments are defined in terms of Boolean operators taken from a clone in Post's lattice.

Share this: