# MAX 1 in 2 SAT Algorithm

The maximum satisfiability problem (Max-Sat) is the problem of finding the maximum number of clauses that can be satisified in a Boolean satisfiability instance. The exactly 1 in 2 Sat problem asks, given a set of clauses each with two literals, is there a set of literals such that each clause has exactly one literal from this set.

The Complexity of Making Unique Choices: Approximating 1-in-k SAT by Guruswami and Trevisan gives a method for approximating Max 1 in 2 Sat. They state monotone (no negated literals) Max 1 in 2 Sat "admits an e-approximation in polynomial time".

I would like to find an exact algorithm for the Max monotone 1 in 2 Sat problem.

• Monotone 1-in-Ek admits an $e$-approximation, but this is interesting only for $k\geq 4$: for $k <4$ a random assignment does better. Monotone 1-in-E2 is MaxCut and admits a $1.138$-approximation given by the Goemans-Williamson algorithm. – Sasho Nikolov Aug 22 '14 at 16:35

An exact algorithm for the Max Monotone 1 in 2 Sat problem (i.e., MaxCut) running faster than $2^n$ (about $O(1.8^n)$ time) can be found in Chapter 6 of my PhD thesis, here: http://web.stanford.edu/~rrwill/thesis.pdf
I don't know of another exact algorithm for the problem that improves over exhaustive search on all instances. For sparse instances (with $O(n)$ clauses), Greg Sorkin and his coauthors have a number of algorithmic results. See here: https://sites.google.com/site/gregorysorkin/pubx