Authors
Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, Anders Yeo
Publication date
2011/11
Journal
Algorithmica
Volume
61
Pages
638-655
Publisher
Springer-Verlag
Description
We present an exact algorithm that decides, for every fixed r≥2 in time whether a given multiset of m clauses of size r admits a truth assignment that satisfies at least ((2 r −1)m+k)/2 r 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(9 r 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 …
Total citations
Scholar articles
N Alon, G Gutin, EJ Kim, S Szeider, A Yeo - Algorithmica, 2011
G Gutin, EJ Kim, S Szeider, A Yeo - arXiv preprint arXiv:0907.4573, 2009
N Alon, G Gutin, EJ Kim, S Szeider, A Yeo - Proc. SODA 2010