### Abstract

We present an exact algorithm that decides, for every fixed r ≥ 2 in time O(m) + 2^{O(k2)} whether a given set 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, 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(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(k^{2}), 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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms |

Publisher | Association for Computing Machinery (ACM) |

Pages | 511-517 |

Number of pages | 7 |

ISBN (Print) | 9780898717013 |

DOIs | |

State | Published - Jan 1 2010 |

Externally published | Yes |

Event | 21st Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, United States Duration: Jan 17 2010 → Jan 19 2010 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 21st Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country | United States |

City | Austin, TX |

Period | 1/17/10 → 1/19/10 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Solving MAX-r-SAT above a tight lower bound'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 511-517). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery (ACM). https://doi.org/10.1137/1.9781611973075.44