{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:19:58Z","timestamp":1777645198583,"version":"3.51.4"},"reference-count":0,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T00:00:00Z","timestamp":1427846400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2015,4]]},"abstract":"<jats:p>We consider the weighted satisfiability problem for Boolean circuits and propositional formul\u00e6, where the weight of an assignment is the number of variables set to true. We study the parameterized complexity of these problems and initiate a systematic study of the complexity of its fragments. Only the monotone fragment has been considered so far and proven to be of same complexity as the unrestricted problems. Here, we consider all fragments obtained by semantically restricting circuits or formul\u00e6 to contain only gates (connectives) from a fixed set B of Boolean functions. We obtain a dichotomy result by showing that for each such B, the weighted satisfiability problems are either W[P]-complete (for circuits) or W[SAT]-complete (for formul\u00e6) or efficiently solvable. We also consider the related enumeration and counting problems.<\/jats:p>","DOI":"10.3233\/fi-2015-1159","type":"journal-article","created":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T01:25:31Z","timestamp":1575336331000},"page":"297-316","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":4,"title":["Parameterized Complexity of Weighted Satisfiability Problems: Decision, Enumeration, Counting"],"prefix":"10.1177","volume":"136","author":[{"given":"Nadia","family":"Creignou","sequence":"first","affiliation":[{"name":"Aix-Marseille Universit\u00e9, CNRS, LIF UMR 7279, 13288, Marseille, France. creignou@lif.univ-mrs.fr"}]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Theoretische Informatik, Leibniz Universit\u00e4t Hannover, Appelstr. 4, 30167 Hannover, Germany. vollmer@thi.uni-hannover.de"}]}],"member":"179","published-online":{"date-parts":[[2015,4,1]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2015-1159","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2015-1159","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:31:37Z","timestamp":1777444297000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2015-1159"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4]]},"references-count":0,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["10.3233\/FI-2015-1159"],"URL":"https:\/\/doi.org\/10.3233\/fi-2015-1159","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4]]}}}