On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Information and Computation Année : 2017

On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability

Résumé

We consider the weighted monotone and antimonotone satisfiability problems on normalized circuits of depth at most t≥2, abbreviated WSAT+[t] and WSAT-[t], 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 WSAT+[t] and WSAT-[t] 2 problems in a straightforward manner. We study the parameterized complexity of WSAT+[t] and WSAT-[t] 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.
Fichier principal
Vignette du fichier
Circuit_Genus.pdf (465.88 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01689398 , version 1 (22-01-2018)

Identifiants

Citer

Iyad Kanj, Dimitrios M. Thilikos, Ge Xia. On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability. Information and Computation, 2017, 257 (139-156), ⟨10.1016/j.ic.2017.11.002⟩. ⟨hal-01689398⟩
88 Consultations
119 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More