<p>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: <a href="http://web.stanford.edu/~rrwill/thesis.pdf">http://web.stanford.edu/~rrwill/thesis.pdf</a></p>

<p>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: <a href="https://sites.google.com/site/gregorysorkin/pubx">https://sites.google.com/site/gregorysorkin/pubx</a></p>

CC BY-SA 3.0
2014-08-24T04:27:29.603Z
Thanks. Dimitris Achlioptas has proven the [phase transition clause to variable ratio](http://tuvalu.santafe.edu/~moore/pubs/soda.html) for 1 in 3 SAT is 1/3. Solvable 1 in 3 SAT instances will have associated graphs with low edge to vertices ratios.
Russell Easterly
CC BY-SA 3.0
2014-08-24T05:54:59.300Z
@RussellEasterly Not really, this is only true for *most* solvable instances.
Sasho Nikolov
CC BY-SA 3.0
2014-08-22T22:13:42.377Z
2014-08-22T22:13:42.377Z
Ryan Williams
<p>A monotone 1-in-2 clause demands that the two variables have different values. Thus, you can model the problem as a graph problem, with one vertex per variable which is to be colored black or white, and an edge for a clause indicating the colors need to be different. Thus, the question is to make the graph bipartite by deleting a minimum number of edges. This is the <a href="http://en.wikipedia.org/wiki/Maximum_cut">MaxCut</a> or Edge Bipartization problem. It is NP-hard.</p>

<p>For Edge Bipartization, there is <a href="http://dx.doi.org/10.1016/j.jcss.2006.02.001">an algorithm</a> that runs fast when few edges need to be deleted. I wrote an implementation for a slightly more general problem described <a href="http://dx.doi.org/10.7155/jgaa.00177">here</a> (<a href="http://www.user.tu-berlin.de/hueffner/bsg/">source code</a>).</p>

CC BY-SA 3.0
2014-08-24T03:20:27.010Z
Thanks. There is a simple way to transform the monotone [Exactly 1 in 3 SAT problem](http://home.comcast.net/~logiclab/EvenSat.html) into a max weighted independent set problem. If an instance is solvable then the associated graph can be made bipartite by removing one edge from each clause. I am hoping certain properties of 1 in 3 SAT will make MaxCut easier on these types of graphs. For example, 1 in 3 SAT has powerful [reduction rules](http://mathforum.org/kb/thread.jspa?forumID=13&threadID=1506736&messageID=5425587#5425587).
Russell Easterly
CC BY-SA 3.0
2014-08-22T07:13:33.637Z
2014-08-22T11:27:24.293Z
2014-08-22T11:27:24.293Z
Falk Hüffner
<p>The <a href="http://en.wikipedia.org/wiki/Maximum_satisfiability_problem">maximum satisfiability problem (Max-Sat)</a> is the problem of finding the maximum number of clauses that can be satisified in a Boolean satisfiability instance. The <a href="http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Exactly-1_3-satisfiability">exactly 1 in 2 Sat problem</a> 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.</p>

<p><a href="http://theory.stanford.edu/~trevisan/pubs/gt05.pdf">The Complexity of Making Unique Choices: Approximating 1-in-k SAT</a> 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".</p>

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

CC BY-SA 3.0
2014-08-22T16:35:42.837Z
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
<graph-algorithms><sat><max2sat>
MAX 1 in 2 SAT Algorithm
Russell Easterly
# MAX 1 in 2 SAT Algorithm

(Asked by: username_0 on 2014-08-22)

The [maximum satisfiability problem (Max-Sat)](http://en.wikipedia.org/wiki/Maximum_satisfiability_problem) 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](http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Exactly-1_3-satisfiability) 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](http://theory.stanford.edu/~trevisan/pubs/gt05.pdf) 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.

**Tags:** graph-algorithms, sat, max2sat

> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_3 on 2014-08-22. Score: 17 | Accepted answer

A monotone 1-in-2 clause demands that the two variables have different values. Thus, you can model the problem as a graph problem, with one vertex per variable which is to be colored black or white, and an edge for a clause indicating the colors need to be different. Thus, the question is to make the graph bipartite by deleting a minimum number of edges. This is the [MaxCut](http://en.wikipedia.org/wiki/Maximum_cut) or Edge Bipartization problem. It is NP-hard.

For Edge Bipartization, there is [an algorithm](http://dx.doi.org/10.1016/j.jcss.2006.02.001) that runs fast when few edges need to be deleted. I wrote an implementation for a slightly more general problem described [here](http://dx.doi.org/10.7155/jgaa.00177) ([source code](http://www.user.tu-berlin.de/hueffner/bsg/)).

> **Comments:**
> **username_0**: Thanks. There is a simple way to transform the monotone [Exactly 1 in 3 SAT problem](http://home.comcast.net/~logiclab/EvenSat.html) into a max weighted independent set problem. If an instance is solvable then the associated graph can be made bipartite by removing one edge from each clause. I am hoping certain properties of 1 in 3 SAT will make MaxCut easier on these types of graphs. For example, 1 in 3 SAT has powerful [reduction rules](http://mathforum.org/kb/thread.jspa?forumID=13&threadID=1506736&messageID=5425587#5425587).  

---

### Answer by username_2 on 2014-08-22. Score: 14

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>

> **Comments:**
> **username_0**: Thanks. Dimitris Achlioptas has proven the [phase transition clause to variable ratio](http://tuvalu.santafe.edu/~moore/pubs/soda.html) for 1 in 3 SAT is 1/3. Solvable 1 in 3 SAT instances will have associated graphs with low edge to vertices ratios.  
> **username_1**: @RussellEasterly Not really, this is only true for *most* solvable instances.  

---

