On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability

Iyad Kanj, Dimitrios M. Thilikos, Ge Xia

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the weighted monotone and antimonotone satisfiability problems on normalized circuits of depth at most t≥2, abbreviated [Figure presented] and [Figure presented], respectively, where the parameter under consideration is the weight of the sought satisfying assignment. These problems model the weighted satisfiability of monotone and antimonotone propositional formulas, and serve as the canonical problems in the definition of the parameterized complexity hierarchy. Moreover, several well-studied problems, including important graph problems, can be modeled as [Figure presented] and [Figure presented] problems in a straightforward manner. We study the parameterized complexity of [Figure presented] and [Figure presented] with respect to the genus of the underlying circuit. We give tight results, and draw a map of the parameterized complexity of these problems with respect to the genus of the circuit. As a byproduct of our results, we obtain tight characterizations of the parameterized complexity of several problems with respect to the genus of the underlying graph.

Original languageEnglish (US)
Pages (from-to)139-156
Number of pages18
JournalInformation and Computation
Volume257
DOIs
StatePublished - Dec 2017

Keywords

  • Genus
  • Parameterized complexity
  • Weighted satisfiability

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability'. Together they form a unique fingerprint.

Cite this