Hot answers tagged

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 fixed-parameter tractable when parameterized by the treewidth of the incidence graph. Samer and Szeider gave an efficient dynamic programming algorithm. References S. Szeider. On fixed-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