%From: haglin@epsilon.cs.mankato.msus.edu (David J. Haglin)
%Subject: PPL Paper
%To: challenge@dimacs.rutgers.edu
%Date: Mon, 21 Dec 92 15:42:14 CST
\input amstex
\let\myfootnote\plainfootnote
\def\footnote"#1"{\myfootnote{#1}}
%%      \input vanilla.sty
\font\tenbf=cmbx10
\font\tenrm=cmr10
\font\tenit=cmti10
\font\ninebf=cmbx9
\font\ninerm=cmr9
\font\nineit=cmti9
\font\eightbf=cmbx8
\font\eightrm=cmr8
\font\eightit=cmti8
\font\sevenrm=cmr7
\TagsOnRight
\nopagenumbers
\def\qed{\hbox{${\vcenter{\vbox{
    \hrule height 0.4pt\hbox{\vrule width 0.4pt height 6pt
    \kern5pt\vrule width 0.4pt}\hrule height 0.4pt}}}$}}
\def\Proof{{\tenbf Proof.}}
\hsize=5.0truein
\vsize=7.8truein
\parindent=15pt
\baselineskip=10pt
\line{\eightrm Parallel Processing Letters \hfil}
\line{\eightrm $\copyright$\, World Scientific Publishing Company \hfil}
\vglue 5pc
\baselineskip=13pt
\centerline{\tenbf APPROXIMATING MAXIMUM 2-CNF SATISFIABILITY}
\vglue 24pt
\centerline{\eightrm DAVID J. HAGLIN}
\baselineskip=12pt
\centerline{\eightit Computer and Information Sciences Department}
\centerline{\eightit Mankato State University}
\centerline{\eightit Mankato, Minnesota 56002, USA}
\vglue 20pt
\centerline{\eightrm Received {\qquad\qquad} (to be inserted}
\baselineskip=10pt
\centerline{\eightrm Revised {\qquad\qquad} by Publisher)}
\centerline{\eightrm Accepted by {\qquad\quad\,\,\,\,} (Mikhail Atallah)}
\vglue 16pt
\centerline{\eightrm ABSTRACT}
{\rightskip=1.5pc
 \leftskip=1.5pc
\eightrm\baselineskip=10pt\parindent=1pc
A parallel approximation algorithm for the MAXIMUM 2-CNF SATISFIABILITY
problem is presented.  This algorithm runs in $O(\log^2 (n + |F|))$
parallel time on a CREW PRAM machine using $O(n + |F|)$ processors,
where n is the number of variables and $|F|$ is the number
of clauses.  Performance guarantees are considered for three slightly
differing definitions of this problem.
\vglue 5pt
\noindent
{\eightit Keywords}\/: Satisfiability, Maximum 2-CNF SAT, Maximum Cut,
Approximation Algorithm.
\vglue 12pt}
\baselineskip=13pt
\line{\tenbf 1. Introduction \hfil}
\vglue 5pt
A {\tenit satisfiability} problem takes as input a formula which
is a conjunction of clauses $F = ( c_1, \ldots , c_m )$.
Let $|F|$ denote $m$, the number of clauses in $F$.
Each clause $c_i$ is a disjunction of $r_i$ literals, where
each literal is either a positive (true) or negative (false)
appearance of a variable from the set $X = \{x_1, \ldots , x_n \}$.
Such a boolean formula is said to be in {\tenit conjunctive
normal form} (CNF).
The objective is to find a truth assignment of the $n$ variables
that satisfies (makes the boolean clause true) either all clauses
or as many of the clauses as possible.
There are several variations of satisfiability problems.
The most widely studied is called CNF SAT:  Given a CNF boolean
expression, is there an assignment
of the variables that satisfies the entire expression?
A related problem is called MAX CNF SAT:  Given a CNF boolean expression,
find an assignment of the variables
satisfying the maximum number of clauses.
There are various restricted versions
of these problems where $|c_i|$ (the number of
literals in clause $i$) is limited.
When the size of each clause
is restricted to $k$ literals, the above problems are referred to as
$k$-CNF SAT and MAX $k$-CNF SAT respectively.

%% \headline={\ifodd\pageno\rightheadline\else\leftheadline\fi}
%% \def\rightheadline{\eightit\hfil \eightrm\folio}
%% \def\leftheadline{\eightrm\folio\hfil\eightit \hfil}
%% \voffset=2\baselineskip

It is known that for $k \geq 3$ the $k$-CNF SAT
problem is NP-Complete [1] but
the 2-CNF SAT problem is in P [2].
Interestingly, the MAX $k$-CNF SAT problem is NP-Complete
for $k \geq 2$ [3].  
So, the 2-CNF SAT problem is solvable in polynomial
time but the MAX 2-CNF SAT problem is NP-Complete.
Recently it was shown
that the 2-CNF SAT problem can be solved in $O( \log n)$ parallel time on a
CRCW PRAM machine using $O(n^4)$ processors [4], where $n$ is
the number of variables in the boolean formula.
Even though good serial approximation algorithms exist
for the MAX CNF SAT problem [5,6],
no fast {\tenit parallel} approximation
algorithm for the MAX 2-CNF SAT problem has been presented.
The parallel algorithm proposed in this paper is a direct result
of a new reduction from the Maximum 2-CNF Satisfiability problem
to the Maximum Cut problem.
The fact that the approximability of these two problems are related
is not surprising since they are both known to be MAX-SNP Complete
[7].

There are several possible interpretations of the word ``restricted'' when
applied to the size of a clause.  Three are considered in this paper :

$\bullet$ {\tenbf Interpretation 1:}
        There are at most $k$ literals per clause.

$\bullet$ {\tenbf Interpretation 2:}
        There are at most $k$ literals per clause
	and if a one-literal clause exists, say $x_i$, then
        a one-literal clause $\bar{x_i}$ cannot exist.
	Also, no repetition of clauses is allowed.

$\bullet$ {\tenbf Interpretation 3:}  There are exactly $k$ literals per clause.

\vglue 12pt
\line{\tenbf 2. Previous Results \hfil}
\vglue 5pt
D. Johnson gave an approximation algorithm (called B2)
for the MAX $k$-CNF SAT problem that satisfies at least
$|F| - \sum_{1 \leq i \leq |F|} 2^{-|c_i |}$ clauses [5].
For interpretation 1, when $k=2$,
this is $1/2 \cdot m_1 + 3/4 \cdot m_2$, where $m_1$
is the number of clauses with exactly one literal
and $m_2$ is the number of clauses with exactly two literals.
For interpretation 3, when $k=2$, this is $3/4 \cdot m$.
Algorithm B2 runs in $O(n \log n)$ serial time
but does not appear to be easily parallelized
because each iteration of the algorithm potentially modifies all of the
clauses in the formula.  We will present an algorithm (called
algorithm MCA for Max Cut Assignment) that achieves the same guarantee of
$1/2 \cdot m_1 + 3/4 \cdot m_2$ for interpretation 1 and
$3/4 \cdot m$ for interpretation 3 in polylogarithmic time.

Lieberherr and Specker gave an approximation algorithm for
interpretation 2 of the MAX 2-CNF SAT problem that guarantees
satisfying at least a ratio of
$h = ( \sqrt{5} - 1)/2 \approx $0.618 (the inverse of the {\tenit golden ratio})
of the total number of clauses,
and they showed this to be P{\tenit -optimal} [6].
Thus, finding an approximation satisfying a ratio $h$ is in P whereas
finding an approximation satisfying a ratio larger than $h$ is NP-Complete.
Their algorithm does not have an obvious parallel equivalent.
One difficulty is that their algorithm generates $O(n^2 )$ potential
solutions from which the maximum satisfying assignment is chosen.
To evaluate one potential solution in parallel can easily be done
in $O( \log |F|)$ time using $O(|F|)$ processors.
But evaluating $O(n^2 )$ potential solutions in parallel requires
$O(n^2 \cdot |F|)$ processors.
Our algorithm MCA runs in $O( \log^2 n)$ parallel time using only
$O(n + |F|)$ processors.
A modification to MCA
tailored to interpretation 2 guarantees that
7/12 $\approx$ 0.583 of the clauses can be satisfied.
Note that this guaranteed ratio is slightly smaller than $h$.
\vglue 12pt
\line{\tenbf 3. Algorithm MCA Description\hfil}
\vglue 5pt
Our proposed algorithm can be described generally as in Figure 1.
The reduction step and the identification step are shown in this section.
Finding an approximation to the maximum cut problem can be done efficiently
in parallel as identified in the following theorem.
\vglue 10pt
{\rightskip=15pt
 \leftskip=15pt
  ALGORITHM MCA
%%  \begin{enumerate}
%%    \item Reduce input satisfiability problem to a maximum cut graph problem.
%%    \item Find an approximation to the maximum cut problem.
%%    \item Identify a truth assignment based on the cut found in step 2.
%%  \end{enumerate}

    $1.$ Reduce input satisfiability problem to a maximum cut graph problem.

    $2.$ Find an approximation to the maximum cut problem.

    $3.$ Identify a truth assignment based on the cut found in step 2.

    END MCA

}
\vglue 5pt
\centerline{\eightrm Fig 1.\,\,\,Parallel Algorithm For MAX 2-CNF SAT}
\vglue 10pt
{\tenbf Theorem 1.}
%% \begin{theorem}\label{MaxCutTheorem}
Given an arbitrary graph $G=(V,E)$ with $n$ nodes and $e$ edges, and
a matching $M \subseteq E$, we can find a cut containing all of the edges in
$M$ plus additional edges whose weights sum to at least
$\frac{weight(E) - weight(M)}{2}$ in $O( \log^2 n )$ parallel time
using $O(n + e)$ processors in the CREW PRAM model. [8] \,\, \qed
%% \end{theorem} 

An alternative proof
of the following lemma has already been given in [5].
But the proof presented here provides an algorithm (see Figure 1)
which can efficiently be run in parallel.

{\tenbf Lemma 2.}
%% \begin{lemma}\label{LowerBoundLemma}
Given a boolean formula $F$ in 2-CNF, there exists a variable assignment
satisfying at least $1/2 \cdot m_1 + 3/4 \cdot m_2$ clauses, where
$m_1$ is the number of clauses with exactly one literal, and $m_2$
is the number of clauses with exactly two literals.
%% \end{lemma}

\Proof
There are three steps to constructing a variable assignment satisfying
the desired number of clauses.  The first step deals with only the
{\tenit two-literal} clauses.  
Given an instance of a boolean formula $F$
in 2-CNF, a graph $G$ is constructed in the following manner :

\vglue 5pt

%% \begin{enumerate}
%%  \item The graph has two nodes corresponding to each variable $x_i$ in $F$,
{\parindent=-15pt\rightskip=15pt\leftskip=30pt

     1. The graph has two nodes corresponding to each variable $x_i$ in $F$,
     one node labeled $x_i$ for the positive assignment of the variable and
     another node labeled $\bar{x_i}$ for the negative assignment of the
     variable.

%%  \item There is an edge between every pair of nodes $x_i$ and
     2. There is an edge between every pair of nodes $x_i$ and
     $\bar{x_i}$ which will be considered part of the matching $M$.

%%  \item For each two-literal clause in $F$, an edge is created
     3. For each two-literal clause in $F$, an edge is created
     between the two nodes corresponding to the literals in the clause.
     If repeated clauses are allowed, the edge will carry a weight
     representing the number of repetitions of the clause.  Otherwise,
     the weight of each edge will be a value of one.

%% \end{enumerate}
}
\vglue 10pt
Because there is a matched edge between every pair of literal nodes
$x_i$ and $\bar{x_i}$, any maximum cut
found by Theorem 1 will exhibit two vertex sets $X$
and $Y = V-X$ such that for every $x_i$ and $\bar{x_i}$ pairs,
either $x_i \in X$ and $\bar{x_i} \in Y$ or
$x_i \in Y$ and $\bar{x_i} \in X$.
If either set $X$ or $Y$ is chosen to represent an
assignment of literals to a value of {\tenit true},
it is easily seen that this gives rise to a certain truth
assignment of the variables by setting $x_i$ to {\tenit true} if literal
$x_i$ is in the set, and setting $x_i$ to {\tenit false} if literal
$\bar{x_i}$ is in the set.
Furthermore, for
every edge in the cut that is not one of the original edges in the
matching $M$, there is a corresponding clause
(possibly repeated) which will be satisfied given either choice
for the set of {\tenit true} literals since exactly one of the literals
in the clause will be true.
Therefore, by Theorem 1,
at least 1/2 of the two-literal clauses are already
guaranteed to be satisfied if the variable assignment is chosen by
selecting either $X$ or $Y$ to be the {\tenit true} literals.
Invoking Theorem 1 to find vertex sets $X$ and $Y$
constitute step 2 of algorithm MCA.

Step 3 of algorithm MCA consists of making an intelligent selection of
either $X$ or
$Y$ to be the set of {\tenit true} literals.  Denote by $\bar{m_2}$
the number of two-literal clauses {\tenit not} in the cut.  There
are $\bar{m_2} + m_1 = y$ clauses involved in the step 3
selection.  Each node in the graph $G$ is {\tenit weighted} by the number
of one-literal clauses in $F$ containing
the literal associated with the node.  Then, both sets $X$ and $Y$
are evaluated by summing the weights of all of the edges in the graph
with both endpoints in the set and also the weights of the nodes in
the set.  Let $z$ and $\bar{z}$ denote this evaluation of $X$ and
$Y$ respectively.  Then, it is clear that $z + \bar{z} = y$.
By selecting $X$ or $Y$ based on the larger of the two values
$z$ and $\bar{z}$, the pigeon hole principle guarantees that at least
half of the $y$ clauses will be satisfied.
Assuming $x$ two-literal clauses are satisfied from the cut,
$y = (m_2 - x) + m_1$.
Thus, at least
$y/2 + x = (m_2 + m_1 + x)/2$
total clauses are satisfied.
Since $x \geq 1/2 \cdot m_2$ by
the Theorem 1,
there must be at least
$1/2 \cdot m_1 + 3/4 \cdot m_2$ total clauses satisfied. \,\, \qed

The algorithm implied by Lemma 2
(see Figure 1) does not
address the translation from the input of 
clauses to the corresponding graph.
If the input were restricted to unique clauses with repetition counts,
the construction of the graph in unit parallel time using
$O(|F|)$ processors is straightforward:  each processor is assigned to
one of the clauses which gives rise to a unique edge in the graph
needing weight equal to the repetition count.
But an algorithm is much stronger if it accepts inputs 
of clauses in any order with repetition allowed.
Translating from this general input to clauses with repetition counts
can be done quickly in parallel using well known techniques.
First the clauses in $F$ are sorted which can be done in $O( \log |F|)$
parallel time using $O(|F| / \log |F|)$ processors by any of several 
parallel sorting algorithms (e.g. [9]).
Then an operation known as {\tenit segmented prefix} is done
which has a running time of $O( \log |F| )$ using $O( |F| / \log |F| )$
processors (e.g. [10]).
Therefore the more general input form can be handled by the simple
translation described above.
Henceforth the exact form of the input (unique clauses
with repetition counts vs. clauses in any order with repetitions allowed)
will not be distinguished since all claims require at least
$O( \log |F| )$ time using at least $O( |F| / \log |F| )$ processors.

{\tenbf Theorem 3.}
%% \begin{theorem}
Given a boolean formula $F$ in 2-CNF, a variable assignment satisfying
at least $1/2 \cdot m_1 + 3/4 \cdot m_2$ clauses can be found in
$O( \log^2 (n + |F|))$ parallel time on a CREW PRAM machine
using $O(n + |F|)$
processors, where $n$ is the number of variables and $|F|$ is the number
of clauses in $F$.
%% \end{theorem}

\Proof
The graph used by Lemma 2 can be constructed in
$O( 1 )$ time using $O(n + |F|)$ processors (see discussion above).
The constructed graph has exactly $2n$ vertices and at most $|F|$ edges.
So, Theorem 1 requires $O( \log^2 n)$ time
and $O(n + |F|)$ processors.
Finally, the two sets in step 3 of Lemma 2
can be evaluated in $O( \log n + |F|)$ time using $O( n + |F| )$
processors.  Thus, the total running time is $O( \log^2 n)$
when $O(n + |F|)$ processors are available. \,\, \qed

An obvious serial version of algorithm MCA improves upon
algorithm B2's running time, albeit for only a subset of
the instances handled by algorithm B2.
The proof of the serial version is identical to the parallel version
and is omitted.
Recall that the approximation to the maximum cut problem
runs in linear serial time.

{\tenbf Theorem 4.}
%% \begin{theorem}
Given a boolean formula $F$ in 2-CNF, a variable assignment satisfying at
least $1/2 \cdot m_1 + 3/4 \cdot m_2$ clauses can be found in
linear serial time. \,\, \qed
%% \end{theorem} 
\vglue 12pt
\line{\tenbf 4. Algorithm MCA for Interpretation 2\hfil}
\vglue 5pt
At first glance, it appears that for interpretation 2, algorithm MCA
guarantees no more than $1/2 \cdot |F|$.
However, slightly modifying algorithm MCA provides a better guarantee.

{\tenbf Theorem 5.}
%% \begin{theorem}
Given a boolean formula $F$ in 2-CNF using {\tenit Interpretation 2},
a variable assignment satisfying at least a ratio of
$7/12 \approx 0.583$ of the clauses
can be found in $O( \log^2 (n + |F|))$ parallel time using
$O(n + |F|)$ processors, where n is the number of variables and $|F|$
is the number of clauses in $F$.
%% \end{theorem}

\Proof
Call a one-literal clause a {\tenit free} clause if the variable
in the one-literal clause does not appear in any of the two-literal
clauses.  Note that by the definition of Interpretation 2, the variable
cannot appear in any other one-literal clause.  So, this free clause is
completely isolated from the rest of the clauses.  This isolation allows
the free clause
to be satisfied (by selecting the appropriate truth value for the variable)
without impacting the satisfiability of the rest of the clauses.  The intent
is to modify algorithm MCA to:  detect free clauses, select the appropriate
truth value for the free clause variables, and run the rest of the clauses
through the algorithm of Lemma 2.
Clearly, the worst case performance of the
modified MCA is when there are no free clauses and, considering MCA's
performance of $1/2 \cdot m_1 + 3/4 \cdot m_2$, the number of
non-free, one-literal clauses is as large as possible.
Notice that
the number of non-free, one-literal clauses can be no more than
twice the number of two-literal clauses.
So, $m_1 \leq 2 m_2$.
The algorithm clearly satisfies at least $7/4 \cdot m_2$ clauses.
Since in the worst case $m_1 + m_2 = |F|$ and $m_1 = 2 m_2$,
$m_2 = |F| / 3$.
Thus in this case at least $7/12 \cdot |F|$ clauses are satisfied. \,\, \qed
\vglue 12pt
\line{\tenbf 5. Approximating Interpretation 3 for any $k$\hfil}
\vglue 5pt
Let $r(n) = (n-1)/n$ for $n$ even and $r(n) = n/(n+1)$ for $n$ odd.
(Note that $r(n)$ is a step function with jumps occurring at a distance
of 2 apart.)
Now, for this interpretation of MAX $k$-CNF SAT, we show how to find,
in parallel, an assignment of the variables
satisfying at least a ratio of $(1+r(k))/2$ of the $|F|$ clauses
in the boolean formula $F$.
This is clearly inferior to the serial
algorithm of [5], except for the small values of $k \leq 3$.

{\tenbf Theorem 6.}
%% \begin{theorem}
Given a boolean formula $F$ in $k$-CNF using Interpretation 3,
a variable assignment satisfying at least a ratio of
$(1+r(k))/2$ of the clauses
can be found in $O( \log^2 (n + |F|))$ parallel time using
$O(n+|F|)$ processors, where $n$ is the number of variables and
$|F|$ is the number of clauses in $F$.
%% \end{theorem}

\Proof
As in algorithm MCA, we utilize the results from the
Theorem 1.
The graph $G$ is constructed similarly to the graph
of Lemma 2.
Note that each $k$-clause will contribute a total edge weight of
$\left( ^k_2 \right)$ to $G$.
Thus, if the boolean formula has $|F|$ clauses, the graph $G$ will have
a total edge weight of $|F| \cdot k(k-1)/2$.
Now we invoke Theorem 1 to find a
cut with at least half of the edges.
(Recall that we construct a graph with a predefined matching
which makes $1/2$ the lower bound ratio instead of $1/2 + 1/2n$.)
Let us consider the minimum number of clauses with at least one of its
corresponding edges {\tenit in} the cut.
Since each clause has a corresponding subgraph $K_k$ in the constructed
graph $G$, each clause can contribute at most $k^2/4$ edges to the
maximum cut if $k$ is even, and at most $(k^2 -1)/4$ edges to the 
maximum cut if $k$ is odd.
Noting that there is at least $|F| \cdot k(k-1)/4$ weight in the cut,
we must have at least $|F| \cdot (k-1)/k$ for $k$ even, or at least
$|F| \cdot k/(k+1)$ for $k$ odd, of the clauses with at least one of its
related edges {\tenit in} the cut.
Thus, the ratio of clauses with at least one edge in the cut is at least
our specially defined function $r(k)$.
Now we simply compute which of the two vertex subsets to assign as the
set of {\tenit true} variables (as in Lemma 2)
which provides us with the
additional satisfied clauses (half of those not part of the cut), thus
guaranteeing the claimed ratio of $(1+r(k))/2$. \,\, \qed
\vglue 12pt
\line{\tenbf 6. Conclusion \hfil}
\vglue 5pt
The technique of building a graph from some problem, especially 
a graph with a ``predefined'' matching, then using the maximum cut
approximation algorithm to find an approximation to the original
problem, is a nice method of producing parallel approximation algorithms.
\vglue 12pt
\line{\tenbf Acknowledgements \hfil}
\vglue 5pt
The author wishes to thank S.M. Venkatesan for suggesting this problem
and for many helpful discussions.
The author also wishes to thank two anonymous referees whose careful
reading has substantially improved this paper.
\vglue 12pt
\line{\tenbf References \hfil}
\vglue 5pt
\medskip
\ninerm
\baselineskip=11pt
\frenchspacing
%% \bibitem{coo-71}
\item{1.}
S. Cook,
The complexity of theorem-proving procedures,
{\nineit Proc. 3rd Annual ACM Symposium on Theory of Computing},
1971, 151--158.
%% \bibitem{eis-76}
\item{2.}
S. Even, A. Itai and A. Shamir,
On the complexity of timetable and multicommodity flow problems,
{\nineit SIAM J. Computing} {\ninebf 5} (1976) 691--703.
%% \bibitem{gjs-76}
\item{3.}
M. Garey, D.S. Johnson and L. Stockmeyer,
Some simplified NP-complete graph problems,
{\nineit Theoretical Computer Science} {\ninebf 1} (1976) 237--267.
%% \bibitem{cl-88}
\item{4.}
S. Cook and M. Luby,
A simple parallel algorithm for finding a satisfying truth assignment
to a 2-CNF formula,
{\nineit Information Processing Letters}, {\ninebf 27} (1988) 141--145.
%% \bibitem{j-74}
\item{5.}
D.S. Johnson,
Approximation algorithms for combinatorial problems,
{\nineit J. Comput. System Sci.} {\ninebf 9} (1974) 256--278.
%% \bibitem{ls-81}
\item{6.}
K.J. Lieberherr and E. Specker,
Complexity of partial satisfaction,
{\nineit Journal of the ACM} {\ninebf 28} (1981) 411--421.
%% \bibitem{py-88}
\item{7.}
C.H. Papadimitriou and M. Yannakakis,
Optimization, Approximation, and Complexity Classes,
{\nineit Proc. 20th Annual ACM Symposium on Theory of Computing},
1988, 229--234.
%% \bibitem{hv-91}
\item{8.}
D. Haglin and S. Venkatesan,
Approximation and intractability results for the maximum cut
and its variants,
{\nineit IEEE Transactions on Computers} {\ninebf 40} (1991) 110--113.
%% \bibitem{c-86}
\item{9.}
R. Cole,
Parallel Merge Sort,
{\nineit Proc. 27nd Annual Symposium on Foundations of Computer Science},
1986, 511--516.
%% \bibitem{l-92}
\item{10.}
F.T. Leighton,
{\nineit Introduction to Parallel Algorithms and Architectures},
(Morgan Kaufmann Publishers, San Mateo, California, 1992).
%% Bibliography
%% \bibitem{ds-83}
\item{11.}
E. Dekel and S. Sahni,
Binary trees and parallel scheduling algorithms,
{\nineit IEEE Transactions on Computers} {\ninebf C-32} (1983) 307--315.
%% \bibitem{Hag89}
\item{12.}
D.J. Haglin, Results on Matching, Maximum Cut, and Related Problems,
Ph. D. Thesis, University of Minnesota, 1989.

\vfil\supereject
\bye