caa a22 4500 445805277 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20111101xx s 000 0 eng 10.1007/s00453-010-9428-7 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9428-7 Solving MAX- r -SAT Above a Tight Lower Bound [Elektronische Daten] [Noga Alon, Gregory Gutin, Eun Kim, Stefan Szeider, Anders Yeo] We present an exact algorithm that decides, for every fixed r≥2 in time $O(m)+2^{O(k^{2})}$ whether a given multiset of m clauses of sizer admits a truth assignment that satisfies at least ((2r−1)m+k)/2r clauses. Thus Max-r-Sat is fixed-parameter tractable when parameterized by the number of satisfied clauses above the tight lower bound(1−2−r )m. This solves an open problem of Mahajan et al. (J.Comput. Syst. Sci. 75(2):137-153, 2009). Our algorithm is based on a polynomial-time data reduction procedure that reduces a problem instance to an equivalent algebraically represented problem with O(9r k 2) variables. This is done by representing the instance as an appropriate polynomial, and by applying a probabilistic argument combined with some simple tools from Harmonic analysis to show that if the polynomial cannot be reduced to one of size O(9r k 2), then there is a truth assignment satisfying the required number of clauses. We introduce a new notion of bikernelization from a parameterized problem to another one and apply it to prove that the above-mentioned parameterized Max-r-Sat admits a polynomial-size kernel. Combining another probabilistic argument with tools from graph matching theory and signed graphs, we show that if an instance of Max-2-Sat with m clauses has at least 3k variables after application of a certain polynomial time reduction rule to it, then there is a truth assignment that satisfies at least (3m+k)/4 clauses. We also outline how the fixed-parameter tractability and polynomial-size kernel results on Max-r-Sat can be extended to more general families of Boolean Constraint Satisfaction Problems. Springer Science+Business Media, LLC, 2010 Max SAT nationallicence Fixed-parameter tractable nationallicence Above lower bound nationallicence Kernel nationallicence Bikernel nationallicence Alon Noga Schools of Mathematics and Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel aut Gutin Gregory Department of Computer Science, Royal Holloway, University of London, TW20 0EX, Egham, Surrey, UK aut Kim Eun Department of Computer Science, Royal Holloway, University of London, TW20 0EX, Egham, Surrey, UK aut Szeider Stefan Institute of Information Systems, Vienna University of Technology, 1040, Vienna, Austria aut Yeo Anders Department of Computer Science, Royal Holloway, University of London, TW20 0EX, Egham, Surrey, UK aut Algorithmica Springer-Verlag 61/3(2011-11-01), 638-655 0178-4617 61:3<638 2011 61 453 https://doi.org/10.1007/s00453-010-9428-7 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9428-7 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Alon Noga Schools of Mathematics and Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel aut NATIONALLICENCE 700 1- Gutin Gregory Department of Computer Science, Royal Holloway, University of London, TW20 0EX, Egham, Surrey, UK aut NATIONALLICENCE 700 1- Kim Eun Department of Computer Science, Royal Holloway, University of London, TW20 0EX, Egham, Surrey, UK aut NATIONALLICENCE 700 1- Szeider Stefan Institute of Information Systems, Vienna University of Technology, 1040, Vienna, Austria aut NATIONALLICENCE 700 1- Yeo Anders Department of Computer Science, Royal Holloway, University of London, TW20 0EX, Egham, Surrey, UK aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/3(2011-11-01), 638-655 0178-4617 61:3<638 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer