A new upper bound for $(n,3)$-MAX-SAT

It is still not known whether the satisfiability problem (SAT), and hence maximum satisfiability problem (MAX-SAT), can be solved in time $\operatorname{poly}(|F|)c^n$, for $c<2$, where $c$ is a constant, $n$ is the number of variables, and $F$ is an input formula. However, such bounds are known for some special cases of these problems where the clause length, the maximal number of variable occurrences or the length of the formula is bounded. In this paper, we consider the $(n,3)$-MAX-SAT problem – a special case of MAX-SAT where each variable appears in a formula at most three times. We present a simple algorithm with running time $O^*(2^{n/3})$. As a byproduct we also obtain a polynomially solvable subclass that may be of independent interest.