# Solving MAX-r-SAT above a Tight Lower Bound

Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, Anders Yeo

Research output: Contribution to journalArticlepeer-review

72 Scopus citations

## Abstract

We present an exact algorithm that decides, for every fixed ≥2 in time O(m)+2 O(k2) 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 polynomial cannot be reduced to one of size O(9 r 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.

Original language English (US) 638-655 18 Algorithmica (New York) 61 3 https://doi.org/10.1007/s00453-010-9428-7 Published - Nov 2011 Yes

## All Science Journal Classification (ASJC) codes

• Computer Science(all)
• Computer Science Applications
• Applied Mathematics

## Keywords

• Above lower bound
• Bikernel
• Fixed-parameter tractable
• Kernel
• Max SAT

## Fingerprint

Dive into the research topics of 'Solving MAX-r-SAT above a Tight Lower Bound'. Together they form a unique fingerprint.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8296175,"math_prob":0.6955516,"size":2067,"snap":"2023-40-2023-50","text_gpt3_token_len":479,"char_repetition_ratio":0.098400384,"word_repetition_ratio":0.03154574,"special_character_ratio":0.2259313,"punctuation_ratio":0.054945055,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9730674,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-08T17:19:24Z\",\"WARC-Record-ID\":\"<urn:uuid:23373981-89b0-4fbd-b0ef-c4e238869782>\",\"Content-Length\":\"52003\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:3885c8a1-86c8-4d08-b066-d5420013462a>\",\"WARC-Concurrent-To\":\"<urn:uuid:10dfa789-5bb9-46de-90b9-59279ec41025>\",\"WARC-IP-Address\":\"3.90.122.189\",\"WARC-Target-URI\":\"https://collaborate.princeton.edu/en/publications/solving-max-r-sat-above-a-tight-lower-bound-2\",\"WARC-Payload-Digest\":\"sha1:THI5S5GSEGF62TMALXUFDKHFOY7L7E7H\",\"WARC-Block-Digest\":\"sha1:ENXJG6GMFOWWWWWI4U4BB7AFYUFGEHZS\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100762.64_warc_CC-MAIN-20231208144732-20231208174732-00553.warc.gz\"}"}