The following is an article that will appear in the Encyclopedia of Algorithms.

Maximum 2-satisfiability (2004; Williams)

Ryan Williams, Carnegie Mellon University, www.cs.cmu.edu/~ryanw

INDEX TERMS: Satisfiability, exact algorithms, constraint satisfaction

SYNONYMS: Max 2-SAT

1 PROBLEM DEFINITION
In the maximum 2-satisfiability problem (abbreviated as Max 2-Sat), one is given a Boolean
formula in conjunctive normal form, such that each clause contains at most two literals. The task
is to find an assignment to the variables of the formula such that a maximum number of clauses is
satisfied.
Max 2-Sat is a classic optimization problem. Its decision version was proved NP-complete
by Garey, Johnson, and Stockmeyer [7], in stark contrast with 2-Sat which is solvable in linear
time [2]. To get a feeling for the difficulty of the problem, the NP-completeness reduction is sketched
here. One can transform any 3-Sat instance F into a Max 2-Sat instance F ′ , by replacing each
clause of F such as

ci = (ℓ1 ∨ ℓ2 ∨ ℓ3 ),

where ℓ1 , ℓ2 , and ℓ3 are arbitrary literals, with the collection of 2-CNF clauses

(ℓ1 ), (ℓ2 ), (ℓ3 ), (ci ), (¬ℓ1 ∨ ¬ℓ2 ), (¬ℓ2 ∨ ¬ℓ3 ), (¬ℓ1 ∨ ¬ℓ3 ), (ℓ1 ∨ ¬ci ), (ℓ2 ∨ ¬ci ), (ℓ3 ∨ ¬ci ),

where ci is a new variable. The following are true:

• If an assignment satisfies ci , then exactly seven of the ten clauses in the 2-CNF collection can
be satisfied.

• If an assignment does not satisfy ci , then exactly six of the ten clauses can be satisfied.

If F is satisfiable then there is an assignment satisfying 7/10 of the clauses in F ′ , and if F is not
satisfiable then no assignment satisfies 7/10 of the clauses in F ′ . Since 3-Sat reduces to Max
2-Sat, it follows that Max 2-Sat (as a decision problem) is NP-complete.

Notation A CNF formula is represented as a set of clauses.

The symbols R and Z denote the sets of reals and integers, respectively. The letter ω denotes
the smallest real number such that for all ǫ > 0, n by n matrix multiplication over a ring can be

1
performed in O(nω+ǫ ) ring operations. Currently, it is known that ω < 2.376 [4]. The ring matrix
product of two matrices A and B is denoted by A × B.
Let A and B be matrices with entries from R ∪ {∞}. The distance product of A and B (written
shorthand as A ⊗d B) is the matrix C defined by the formula
C[i, j] = min {A[i, k] + B[k, j]}.
k=1,...,n

A word on m’s and n’s: in reference to graphs, m and n denote the number of edges and the
number of nodes in the graph, respectively. In reference to CNF formulas, m and n denote the
number of clauses and the number of variables, respectively.

2 KEY RESULT
The primary result of this article is a procedure solving Max 2-Sat in O(m · 2ωn/3 ) time. The
method can be generalized to count the number of solutions to any constraint optimization problem
with at most two variables per constraint (cf. [17]), though the presentation in this article shall
be somewhat different from the reference, and much simpler. There are several other known exact
algorithms for Max 2-Sat that are more effective in special cases, such as sparse instances [9, 8,
3, 13, 15, 16, 11, 12]. The procedure described below is the only one known (to date) that runs in
O(poly(m) · 2δn ) time (for some fixed δ < 1) in all possible cases.

2.1 KEY IDEA

The algorithm gives a reduction from Max 2-Sat to the problem Max Triangle, in which
one is given a graph with integer weights on its nodes and edges, and the goal is to output a
3-cycle of maximum weight. At first, the existence of such a reduction sounds strange, as Max
Triangle can be trivially solved in O(n3 ) time by trying all possible 3-cycles. The key is that
the reduction exponentially increases the problem size, from a Max 2-Sat instance with m clauses
and n variables, to a Max Triangle instance having O(22n/3 ) edges, O(2n/3 ) nodes, and weights
in the range {−m, . . . , m}.
Note that if Max Triangle required Θ(n3 ) time to solve, then the resulting Max 2-Sat
algorithm would take Θ(2n ) time, rendering the above reduction pointless. However, it turns out
that the brute-force search of O(n3 ) for Max Triangle is not the best one can do– using fast
matrix multiplication, there is an algorithm for Max Triangle that runs in O(W nω ) time on
graphs with weights in the range {−W, . . . , W }.

2.2 MAIN ALGORITHM

First, a reduction from Max 2-Sat to Max Triangle is described, arguing that each triangle of
weight K in the resulting graph is in one-to-one correspondence with an assignment that satisfies
K clauses of the Max 2-Sat instance. Let a, b be reals, and let Z[a, b] := [a, b] ∩ Z.
Lemma 1. If Max Triangle on graphs with n nodes and weights in Z[−W, W ] is solvable in
O(f (W ) · g(n)) time, for polynomials f and g, then Max 2-Sat is solvable in O(f (m) · g(2n/3 ))
time, where m is the number of clauses and n is the number of variables.

2
Proof: Let C be a given 2-CNF formula. Assume without loss of generality that n is divisible
by 3. Let F be an instance of Max 2-Sat. Arbitrarily partition the n variables of F into three
sets P1 , P2 , P3 , each having n/3 variables. For each Pi , make a list Li of all 2n/3 assignments to
the variables of Pi .
Define a graph G = (V, E) with V = L1 ∪ L2 ∪ L3 and E = {(u, v)|u ∈ Pi , v ∈ Pj , i 6= j}. That
is, G is a complete tripartite graph with 2n/3 nodes in each part, and each node in G corresponds
to an assignment to n/3 variables in C. Weights are placed on the nodes and edges of G as follows.
For a node v, define w(v) to be the number of clauses that are satisfied by the partial assignment
denoted by v. For each edge {u, v}, define w({u, v}) = −Wuv , where Wuv is the number of clauses
that are satisfied by both u and v.
Define the weight of a triangle in G to be the total sum of all weights and nodes in the triangle.

Claim 1. There is a one-to-one correspondence between the triangles of weight K in G and the
variable assignments satisfying exactly K clauses in F .

Proof: Let a be a variable assignment. Then there exist unique nodes v1 ∈ L1 , v2 ∈ L2 , and
v3 ∈ L3 such that a is precisely the concatenation of v1 , v2 , v3 as assignments. Moreover, any triple
of nodes v1 ∈ L1 , v2 ∈ L2 , and v3 ∈ L3 corresponds to an assignment. Thus there is a one-to-one
correspondence between triangles in G and assignments to F .
The number of clauses satisfied by an assignment is exactly the weight of its corresponding
triangle. To see this, let Ta = {v1 , v2 , v3 } be the triangle in G corresponding to assignment a. Then

w(Ta ) = w(v1 ) + w(v2 ) + w(v3 ) + w({v1 , v2 }) + w({v2 , v3 }) + w({v1 , v3 })

X3 X
= |{c ∈ F | vi satisfies F }| − |{c ∈ F | vi and vj satisfy F }|
i=1 i,j : i6=j
= |{c ∈ F | a satisfies F }|,

where the last equality follows from the inclusion-exclusion principle.

Notice that the number of nodes in G is 3 · 2n/3 , and the absolute value of any node and edge
weight is m. Therefore, running a Max Triangle algorithm on G, a solution to Max 2-Sat is
obtained in O(f (m) · g(3 · 2n/3 )), which is O(f (m) · g(2n/3 )) since g is a polynomial. This completes
the proof of Lemma 1.
Next, a procedure is described for finding a maximum triangle faster than brute-force search,
using fast matrix multiplication. Alon, Galil, and Margalit [1] (following Yuval [20]) showed that
the distance product for matrices with entries drawn from Z[−W, W ] can be computed using fast
matrix multiplication as a subroutine.

Theorem 2 (Alon, Galil, Margalit [1]). Let A and B be n×n matrices with entries from Z[−W, W ]∪
{∞}. Then A ⊗d B can be computed in O(W nω log n) time.

Proof: (Sketch) One can replace ∞ entries in A and B with 2W + 1 in the following. Define
matrices A′ and B ′ , where

A′ [i, j] = x3W −A[i,j], B ′ [i, j] = x3W −B[i,j] ,

3
and x is a variable. Let C = A′ × B ′ . Then
X
n
C[i, j] = x6W −A[i,k]−B[k,j].
k=1

The next step is to pick a number x that makes it easy to determine, from the sum of arbitrary
powers of x, the largest power of x appearing in the sum; this largest power immediately gives the
minimum A[i, k] + B[k, j]. Each C[i, j] is a polynomial in x with coefficients from Z[0, n]. Suppose
each C[i, j] is evaluated at x = (n + 1). Then each entry of C[i, j] can be seen as an (n + 1)-ary
number, and the position of this number’s most significant digit gives the minimum A[i, k]+ B[k, j].
In summary, A ⊗d B can be computed by constructing

A′ [i, j] = (n + 1)3W −A[i,j], B ′ [i, j] = (n + 1)3W −B[i,j]

in O(W log n) time per entry, computing C = A′ × B ′ in O(nω · (W log n)) time (as the sizes of
the entries are O(W log n)), then extracting the minimum from each entry of C, in O(n2 · W log n)
time. Note if the minimum for an entry C[i, j] is at least 2W + 1, then C[i, j] = ∞.
Using the fast distance product algorithm, one can solve Max Triangle faster than brute-
force. The following is based on an algorithm by Itai and Rodeh [10] for detecting if an unweighted
graph has a triangle in less than n3 steps. The result can be generalized to counting the number
of k-cliques, for arbitrary k ≥ 3. (To keep the presentation simple, the counting result is omitted.
Concerning the k-clique result, there is unfortunately no asymptotic runtime benefit from using
a k-clique algorithm instead of a triangle algorithm, given the current best algorithms for these
problems.)

Theorem 3. Max Triangle can be solved in O(W nω log n), for graphs with weights drawn from
Z[−W, W ].

Proof: First, it is shown that a weight function on nodes and edges can be converted into an
equivalent weight function with weights on only edges. Let w be the weight function of G, and
redefine the weights to be:

w(u) + w(v)
w′ ({u, v}) = + w({u, v}), w′ (u) = 0.
2
Note the weight of a triangle is unchanged by this reduction.
The next step is to use a fast distance product to find a maximum weight triangle in an edge-
weighted graph of n nodes. Construe the vertex set of G as the set {1, . . . , n}. Define A to
be the n × n matrix such that A[i, j] = −w({i, j}) if there is an edge {i, j}, and A[i, j] = ∞
otherwise. The claim is that there is a triangle through node i of weight at least K if and only
if (A ⊗d A ⊗d A)[i, i] ≤ −K. This is because (A ⊗d A ⊗d A)[i, i] ≤ −K if and only if there are
distinct j and k such that {i, j}, {j, k}, {k, i} are edges and A[i, j] + A[j, k] + A[k, i] ≤ −K, i.e.,
w({i, j}) + w({j, k}) + w({k, i}) ≥ K.
Therefore, by finding an i such that (A ⊗d A ⊗d A)[i, i] is minimized, one obtains a node i
contained in a maximum triangle. To obtain the actual triangle, check all m edges {j, k} to see if
{i, j, k} is a triangle.

4
Theorem 4. Max 2-Sat can be solved in O(m · 1.732n ) time.

Proof: Given a set of clauses C, apply the reduction from Lemma 1 to get a graph G with O(2n/3 )
nodes and weights from Z[−m, m]. Apply the algorithm of Theorem 3 to output a max triangle
in G in O(m · 2ωn/3 log(2n/3 )) = O(m · 1.732n ) time, using the O(n2.376 ) matrix multiplication of
Coppersmith and Winograd [4].

3 APPLICATIONS
By modifying the graph construction, one can solve other problems in O(1.732n ) time, such as Max
Cut, Minimum Bisection, and Sparsest Cut. In general, any constraint optimization problem
for which each constraint has at most two variables can be solved faster using the above approach.
For more details, see [17] and the recent survey by Woeginger [19]. Techniques similar to the above
algorithm have also been used by Dorn [6] to speed up dynamic programming for some problems
on planar graphs (and in general, graphs of bounded branchwidth).

4 OPEN PROBLEMS
• Improve the space usage of the above algorithm. Currently, Θ(22n/3 ) space is needed. A
very interesting open question is if there is a O(1.99n ) time algorithm for Max 2-Sat that
uses only polynomial space. This question would have a positive answer if one could find an
algorithm for solving the k-Clique problem that uses polylogarithmic space and nk−δ time
for some δ > 0 and k ≥ 3.

• Find a faster-than-2n algorithm for Max 2-Sat that does not require fast matrix multipli-
cation. The fast matrix multiplication algorithms have the unfortunate reputation of being
impractical.

• Generalize the above algorithm to work for Max k-Sat, where k is any positive integer.
The current formulation would require one to give an efficient algorithm for finding a small
hyperclique in a hypergraph. However, no general results are known for this problem. It is
1
conjectured that for all k ≥ 2, Max k-Sat is in Õ(2n(1− k+1 ) ) time, based on the conjecture
that matrix multiplication is in n2+o(1) time [17].

5 CROSS REFERENCES
Matrix Multiplication and All Pairs Shortest Paths, CNF SAT and MAXSAT Algorithms, Max
Cut, Minimum Bisection, Sparsest Cut

5
6 RECOMMENDED READING

References
[1] Alon N., Galil Z., and Margalit O. On the exponent of the all-pairs shortest path problem. J.
Computer and System Sciences 54:255–262, 1997.

[2] Aspvall B., Plass M. F., and Tarjan R. E. A linear-time algorithm for testing the truth of
certain quantified boolean formulas. Inf. Proc. Letters 8(3):121–123, 1979.

[3] Bansal N. and Raman V. Upper bounds for Max Sat: Further Improved. In Proceedings of
ISAAC, Springer-Verlag LNCS 1741:247–258, 1999.

[4] Coppersmith D. and Winograd S. Matrix Multiplication via Arithmetic Progressions. JSC
9(3):251–280, 1990.

[5] Dantsin E. and Wolpert A. Max SAT for formulas with constant clause density can be solved
faster than in O(2n ) time. In Proc. of the 9th International Conference on Theory and Appli-
cations of Satisfiability Testing, Springer-Verlag LNCS 4121:266–276, 2006.

[6] Dorn F. Dynamic Programming and Fast Matrix Multiplication. In Proceedings of 14th Annual
European Symposium on Algorithms, Springer-Verlag LNCS 4168:280–291, 2006.

[7] Garey M., Johnson D., and Stockmeyer L. Some simplified NP-complete graph problems.
Theor. Comput. Sci. 1:237–267, 1976.

[8] Gramm J. and Niedermeier R. Faster exact solutions for Max2Sat. In Proceedings of CIAC,
Springer-Verlag LNCS 1767:174–186, 2000.

[9] Hirsch E. A. A 2m/4 -time Algorithm for Max 2-SAT: Corrected Version. Electronic Colloquium
on Computational Complexity Report TR99-036, 2000.

[10] Itai A. and Rodeh M. Finding a Minimum Circuit in a Graph. SIAM J. Comput. 7(4):413–423,
1978.

[11] Kneis J., Mölle D., Richter S., and Rossmanith P. Algorithms Based on the Treewidth of Sparse
Graphs. In Proc. Workshop on Graph Theoretic Concepts in Computer Science, Springer-
Verlag LNCS 3787:385–396, 2005.

[12] Kojevnikov A. and Kulikov A. S. A New Approach to Proving Upper Bounds for Max 2-SAT.
In Proc. of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 11–17,
2006.

[13] Mahajan M. and Raman V. Parameterizing above Guaranteed Values: MAXSAT and MAX-
CUT. J. Algorithms 31(2): 335–354, 1999.

[14] Niedermeier R. and Rossmanith P. New upper bounds for maximum satisfiability. J. Algorithms
26:63–88, 2000.

6
[15] Scott A. and Sorkin G. Faster Algorithms for MAX CUT and MAX CSP, with Polynomial
Expected Time for Sparse Instances. In Proceedings of RANDOM-APPROX 2003, Springer-
Verlag LNCS 2764:382–395, 2003.

[16] Williams R. On Computing k-CNF Formula Properties. In Theory and Applications of Satis-
fiability Testing, Springer-Verlag LNCS 2919:330–340, 2004.

[17] Williams R. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor.
Comput. Sci. 348(2-3): 357–365, 2005.

[18] Woeginger G. J. Exact algorithms for NP-hard problems: A survey. In Combinatorial Opti-
mization - Eureka! You shrink!, Springer-Verlag LNCS 2570:185–207, 2003.

[19] Woeginger G. J. Space and time complexity of exact algorithms: some open problems. In Proc.
1st Int. Workshop on Parameterized and Exact Computation (IWPEC 2004), Springer-Verlag
LNCS 3162, 281-290, 2004.

[20] Yuval G. An Algorithm for Finding All Shortest Paths Using N 2.81 Infinite-Precision Multi-
plications. Inf. Process. Lett. 4(6):155–156, 1976.