Abstract
The natural generalization of the Boolean satisfiability problem to optimization problems is the task of determining the maximum number of clauses that can simultaneously be satisfied in a propositional formula in conjunctive normal form. In the weighted maximum satisfiability problem each clause has a positive weight and one seeks an assignment of maximum weight. The literature almost solely considers the case of positive weights. While the general case of the problem is only restricted slightly by this constraint, many special cases become trivial in the absence of negative weights. In this work we study the problem with negative weights and observe that the problem becomes computationally harder  which we formalize from a parameterized perspective in the sense that various variations of the problem become W[1]hard if negative weights are present.
Allowing negative weights also introduces new variants of the problem: Instead of maximizing the sum of weights of satisfied clauses, we can maximize the absolute value of that sum. This turns out to be surprisingly expressive even restricted to monotone formulas in disjunctive normal form with at most two literals per clause. In contrast to the versions without the absolute value, however, we prove that these variants are fixedparameter tractable. As technical contribution we present a kernelization for an auxiliary problem on hypergraphs in which we seek, given an edgeweighted hypergraph, an induced subgraph that maximizes the absolute value of the sum of edgeweights.
BibTeX  Entry
@InProceedings{bannach_et_al:LIPIcs.SWAT.2022.12,
author = {Bannach, Max and Fleischmann, Pamela and Skambath, Malte},
title = {{MaxSAT with Absolute Value Functions: A Parameterized Perspective}},
booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages = {12:112:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772365},
ISSN = {18688969},
year = {2022},
volume = {227},
editor = {Czumaj, Artur and Xin, Qin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16172},
URN = {urn:nbn:de:0030drops161728},
doi = {10.4230/LIPIcs.SWAT.2022.12},
annote = {Keywords: parameterized complexity, kernelization, weighted maximum satisfiability, absolute value maximization}
}
Keywords: 

parameterized complexity, kernelization, weighted maximum satisfiability, absolute value maximization 
Collection: 

18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) 
Issue Date: 

2022 
Date of publication: 

22.06.2022 