# Tag Info

17

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. ...

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)... 8 To complement the other answer: Costello, Shapira and Tetali showed that the expected approximation ration achieved by Johnson's algorithm on a random permutation of the variables is strictly better than$\frac{2}{3}$. Poloczek and Schnitger showed that another randomized version of the algorithm has expected approximation ratio$\frac{3}{4}$, and that the ... 7 I think it is possible to reduce Max Cut to this problem: given a graph$G(V,E)$, make a variable for each vertex, and for each edge$(u,v)\in E$make the two clauses$(x_u\lor x_v)$and$(\neg x_u\lor\neg x_v)$. In the resulting instance,$x_u$appears$d(x_u)$times positive and the same number of times negative. Since Max Cut is still NP-hard on regular ... 6 One can get a$n \choose n/2$lower bound by considering the$n$variable formula that for every pair$x$,$y$, of variables contains the clauses$(x \vee y)$and$(\neg x \vee \neg y)$. The total number of clauses is$2 \cdot {n \choose 2}$. Every assignment will satisfy one of the two clauses on$x$and$y$. Both clauses are satisfied exactly when$x$and$...

6

This does not answer directly your Max-SAT problem but the references may guide you to the complete answer. Szeider showed that Satisfiability is ﬁxed-parameter tractable when parameterized by the treewidth of the incidence graph. Samer and Szeider gave an eﬃcient dynamic programming algorithm. References S. Szeider. On ﬁxed-parameter tractable ...

6

3-OCC-MAX 2SAT: given a CNF formula $\varphi$ in which each clause contains at most 2 literals and each variable appears in at most three clauses (counting together both positive and negative literals); does there exist an assignment that satisfies at least $k$ clauses? In P. Berman, M. Karpinski, On some tighter inapproximability results (1998). Lecture ...

5

The described algorithm is actually Johnson's algorithm (with order on the vertices) which is known to achieve$\frac{2}{3} ratio$.

2

It sounds like what you want are universal factor graphs. Such graphs exist for every NP-hard boolean CSP and in many cases are optimally inapproximable.

Only top voted, non community-wiki answers of a minimum length are eligible