TY - GEN

T1 - Solving MAX-r-SAT above a tight lower bound

AU - Alon, Noga

AU - Gutin, Gregory

AU - Kim, Eun Jung

AU - Szeider, Stefan

AU - Yeo, Anders

PY - 2010

Y1 - 2010

N2 - We present an exact algorithm that decides, for every fixed r ≥ 2 in time O(m) + 2O(k2) whether a given set of m clauses of size r admits a truth assignment that satisfies at least ((2r - 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, Raman and Sikdar (J. Comput. System Sci., 75, 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(k2) 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(k2), then there is a truth assignment satisfying the required number of clauses. 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 certain polynomial time reduction rules to it, then there is a truth assignment that satisfies at least (3m + k)/4 clauses. We also outline how the fixed-parameter tractability result on MAX-r-SAT can be extended to a family of Boolean Constraint Satisfaction Problems.

AB - We present an exact algorithm that decides, for every fixed r ≥ 2 in time O(m) + 2O(k2) whether a given set of m clauses of size r admits a truth assignment that satisfies at least ((2r - 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, Raman and Sikdar (J. Comput. System Sci., 75, 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(k2) 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(k2), then there is a truth assignment satisfying the required number of clauses. 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 certain polynomial time reduction rules to it, then there is a truth assignment that satisfies at least (3m + k)/4 clauses. We also outline how the fixed-parameter tractability result on MAX-r-SAT can be extended to a family of Boolean Constraint Satisfaction Problems.

UR - http://www.scopus.com/inward/record.url?scp=77951692326&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951692326&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973075.44

DO - 10.1137/1.9781611973075.44

M3 - Conference contribution

AN - SCOPUS:77951692326

SN - 9780898717013

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 511

EP - 517

BT - Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Association for Computing Machinery (ACM)

T2 - 21st Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 17 January 2010 through 19 January 2010

ER -