# The 2-MAXSAT Problem Can Be Solved in Polynomial Time

Yangjun Chen *Y. Chen is with the Department of Applied Computer Science,
University of Winnpeg, Manitoba, Canada, R3B 2E9.
E-mail: see http://www.uwinnipeg.ca/$\sim$ychen2 The article is a modification
and extension of a conference paper: Y. Chen, The 2-MAXSAT Problem Can Be
Solved in Polynomial Time, in Proc. CSCI2022, IEEE, Dec. 14-16, 2022, Las
Vegas, USA, pp. 473-480.

###### Abstract

By the MAXSAT problem, we are given a set $V$ of $m$ variables and a
collection $C$ of $n$ clauses over $V$. We will seek a truth assignment to
maximize the number of satisfied clauses. This problem is NP-hard even for its
restricted version, the 2-MAXSAT problem by which every clause contains at
most 2 literals. In this paper, we discuss an efficient algorithm to solve
this problem. Its worst-case time complexity is bounded by O($n^{3}m^{3}$).
This shows that the 2-MAXSAT problem can be solved in polynomial time.

###### Index Terms:

satisfiability problem, maximum satisfiability problem, NP-hard, NP-complete,
conjunctive normal form, disjunctive normal form.

##  I Introduction

The satisfiability problem is perhaps one of the most well-studied problems
that arise in many areas of discrete optimization, such as artificial
intelligence, mathematical logic, and combinatorial optimization, to just name
a few. Given a set $V$ of Boolean (true/false) variables and a collection $C$
of clauses over $V$, or say, a logic formula in CNF (Conjunctive Normal Form),
the satisfiability problem is to determine if there is a truth assignment that
satisfies all clauses in $C$ [2]. The problem is NP-complete even when every
clause in $C$ has at most three literals [5]. The maximum satisfiability
(MAXSAT) problem is an optimization version of satisfiabiltiy that seeks a
truth assignment to maximize the number of satisfied clauses [8]. This problem
is NP-hard even for its restricted version, the so-called 2-MAXSAT problem, by
which every clause in $C$ has at most two literals [6]. Its application can be
seen in an extensive biliography [3, 6, 11, 14, 15, 16, 17, 19].

Over the past several decades, a lot of research on the MAXSAT has been
conducted. Almost all of them are the approximation methods [8, 10, 18, 20, 1,
4], such as (1-1/$e$)-approximation, 3/4-approximation[20], as well as the
method based on the integer linear programming [9]. The only algorithms for
exact solution are discussed in [22, 21]. The worst-case time complexity of
[22] is bounded by O($b$2m), where $b$ is the maximum number of the ccurrences
of any variable in the clauses of $C$, while the worst-case time complexity of
[21] is bounded by max$\\{$O($2^{m}$), O*($1.2989^{n}$)$\\}$. By both
algorithms, the traditional branch-and-bound method is used for solving the
satisfiability problem, which will search for a solution by letting a variable
(or a literal) be 1 or 0. In terms of [7], any algorithm based on branch-and-
bound runs in O*($c^{m}$) time with $c$ $\geq$ 2.

In this paper, we discuss a polynomial time algorithm to solve the 2-MAXSAT
problem. Its worst-case time complexity is bounded by O($n^{3}m^{3}$), where
$n$ and $m$ are the numbers of clauses and the number of variables in $C$,
respectively. Thus, our algorithm is in fact a proof of $P$ = NP.

The main idea behind our algorithm can be summarized as follows.

  1. 1.

Given a collection $C$ of $n$ clauses over a set of variables $V$ with each
containing at most 2 literals. Construct a formula $D$ over another set of
variables $U$, but in DNF (Disjunctive Normal Form) containing 2$n$
conjunctions with each of them having at most 2 literals such that there is a
truth assignment for $V$ that satisfies at least $n$* $\leq$ $n$ clauses in
$C$ if and only if there is a truth assignment for $U$ that satisfies at least
$n$* conjunctions in $D$.

  2. 2.

For each $D_{i}$ in $D$ ($i$ $\in$ $\\{$1, …, 2$n$$\\}$), construct a graph,
called a $p$*-graph to represent all those truth assignments $\sigma$ of
variables such that under $\sigma$ $D_{i}$ evaluates to true.

  3. 3.

Organize the $p$*-graphs for all $D_{i}$’s into a trie-like graph $G$.
Searching $G$ bottom up, we can find a maximum subset of satisfied
conjunctions in polynomial time.

The organization of the rest of this paper is as follow. First, in Section II,
we restate the definition of the 2-MAXSAT problem and show how to reduce it to
a problem that seeks a truth assignment to maximize the number of satisfied
conjunctions in a formula in DNF. Then, we discuss a basic algorithm in
Section III. Next, in Section IV, we discuss how the basic algorithm can be
improved. Section V is devoted to the analysis of the time complexity of the
algorithm. Finally, a short conclusion is set forth in Section VI.

##  II 2-MAXSAT Problem

We will deal solely with Boolean variables (that is, those which are either
true or false), which we will denote by $c_{1}$, $c_{2}$, etc. A literal is
defined as either a variable or the negation of a variable (e.g., $c_{7}$,
$\neg$$c_{11}$ are literals). A literal $\neg$$c_{i}$ is true if the variable
$c_{i}$ is false. A clause is defined as the OR of some literals, written as
($l_{1}$ $\lor$ $l_{2}$ $\lor$ …. $\lor$ $l_{k}$) for some $k$, where each
$l_{i}$ (1 $\leq$ $i$ $\leq$ $k$) is a literal, as illustrated in
$\neg$$c_{1}$ $\lor$ $c_{11}$. We say that a Boolean formula is in conjunctive
normal form (CNF) if it is presented as an AND of clauses: $C_{1}$ $\land$ …
$\land$ $C_{n}$ ($n$ $\geq$ 1). For example, ($\neg$$c_{1}$ $\lor$ $c_{7}$
$\lor$ $\neg$$c_{11}$) $\land$ ($c_{5}$ $\lor$ $\neg$$c_{2}$ $\lor$
$\neg$$c_{3}$) is in CNF. In addition, a disjunctive normal form (DNF) is an
OR of conjunctions: $D_{1}$ $\lor$ $D_{2}$ $\lor$ … $\lor$ $D_{m}$ ($m$ $\geq$
1). For instance, ($c_{1}$ $\land$ $c_{2}$) $\lor$ ($\neg$$c_{1}$ $\land$
$c_{11}$) is in DNF.

Finally, the MAXSAT problem is to find an assignment to the variables of a
Boolean formula in CNF such that the maximum number of clauses are set to
true, or are satisfied. Formally:

2-MAXSAT

  * •

Instance: A finite set $V$ of variables, a Boolean formula $C$ = $C_{1}$
$\land$ … $\land$ $C_{n}$ in CNF over $V$ such that each $C_{i}$ has 0 <
|$C_{i}$| $\leq$ 2 literals ($i$ = 1, …, $n$), and a positive integer $n$*
$\leq$ $n$.

  * •

Question: Is there a truth assignment for $V$ that satisfies at least $n$*
clauses?

In terms of [6], 2-MAXSAT is NP-complete.

To find a truth assignment $\sigma$ such that the number of clauses set to
$true$ is maximized under $\sigma$, we can try all the possible assignments,
and count the satisfied clauses as discussed in [16], by which bounds are set
up to cut short branches. We may also use a heuristic method to find an
approximate solution to the problem as described in [8].

In this paper, we propose a quite different method, by which for $C$ = $C_{1}$
$\land$ … $\land$ $C_{n}$, we will consider another formula $D$ in DNF
constructed as follows.

Let $C_{i}$ = $c_{i1}$ $\lor$ $c_{i2}$ be a clause in $C$, where $c_{i1}$ and
$c_{i2}$ denote either variables in $V$ or their negations. For $C_{i}$,
define a variable $x_{i}$. and a pair of conjunctions: $D_{i1}$, $D_{i2}$,
where

$D_{i1}$ = $c_{i1}$ $\land$ $x_{i}$,

$D_{i2}$ = $c_{i2}$ $\land$ $\neg$$x_{i}$.

Let $D$ = $D_{11}$ $\lor$ $D_{12}$ $\lor$ $D_{21}$ $\lor$ $D_{22}$ $\lor$ …
$\lor$ $D_{n1}$ $\lor$ $D_{n2}$. Then, given an instance of the 2-MAXSAT
problem defined over a variable set $V$ and a collection $C$ of $n$ clauses,
we can construct a logic formula $D$ in DNF over the set $V$ $\cup$ $X$ in
polynomial time, where $X$ = $\\{$$x_{1}$, …, $x_{n}$$\\}$. $D$ has $m$ = 2$n$
conjunctions.

Concerning the relationship of $C$ and $D$, we have the following proposition.

######  Proposition 1.

Let $C$ and $D$ be a formula in CNF and a formula in DNF defined above,
respectively. No less than $n$* clauses in $C$ can be satisfied by a truth
assignment for $V$ if and only if no less than $n$* conjunctions in $D$ can be
satisfied by some truth assignment for $V$ $\cup$ $X$.

###### Proof.

Consider every pair of conjunctions in $D$: $D_{i1}$ = $c_{i1}$ $\land$
$x_{i}$ and $D_{i2}$ = $c_{i2}$ $\land$ $\neg$$x_{i}$ ($i$ $\in$ $\\{$1, …,
$n$$\\}$). Clearly, under any truth assignment for the variables in $V$ $\cup$
$X$, at most one of $D_{i1}$ and $D_{i2}$ can be satisfied. If $x_{i}$ = true,
we have $D_{i1}$ = $c_{i1}$ and $D_{i2}$ = false. If $x_{i}$ = false, we have
$D_{i2}$ = $c_{i2}$ and $D_{i1}$ = false.

"$\Rightarrow$" Suppose there exists a truth assignment $\sigma$ for $C$ that
satisfies $p$ $\geq$ $n$* clauses in $C$. Without loss of generality, assume
that the $p$ clauses are $C_{1}$, $C_{2}$, …, $C_{p}$.

Then, similar to Theorem 1 of [11], we can find a truth assignment
$\tilde{\sigma}$ for $D$, satisfying the following condition:

For each $C_{j}$ = $c_{i1}$ $\lor$ $c_{i2}$ ($j$ = 1, …, $p$), if $c_{j1}$ is
true and $c_{j2}$ is false under $\sigma$, (1) set both $c_{j1}$ and $x_{j}$
to true for $\tilde{\sigma}$. If $c_{j1}$ is false and $c_{j2}$ is true under
$\sigma$, (2) set $c_{j2}$ to true, but $x_{j}$ to false for $\tilde{\sigma}$.
If both $c_{i1}$ and $c_{i2}$ are true, do (1) or (2) arbitrarily.

Obviously, we have at least $n$* conjunctions in $D$ satisfied under
$\tilde{\sigma}$.

"$\Leftarrow$" We now suppose that a truth assignment $\tilde{\sigma}$ for $D$
with $q$ $\geq$ $n$* conjunctions in $D$ satisfied. Again, assume that those
$q$ conjunctions are $D_{1b_{1}}$, $D_{2b_{2}}$, …, $D_{qb_{q}}$, where each
$b_{j}$ ($j$ = 1, …, $q$) is 1 or 2.

Then, we can find a truth assignment $\sigma$ for $C$, satisfying the
following condition:

For each $D_{jb_{j}}$ ($j$ = 1, …, $q$), if $b_{j}$ = 1, set $c_{j1}$ to true
for $\sigma$; if $b_{j}$ = 2, set $c_{j2}$ to true for $\sigma$.

Clearly, under $\sigma$, we have at lease $n$* clauses in $C$ satisfied.

The above discussion shows that the proposition holds. ∎

Proposition 1 demonstrates that the 2-MAXSAT problem can be transformed, in
polynomial time, to a problem to find a maximum number of conjunctions in a
logic formula in DNF.

As an example, consider the following logic formula in CNF:

$\begin{array}[]{ll}C=C_{1}\land C_{2}\land C_{3}\\\ \hskip
11.38092pt=(c_{1}\lor c_{2})\land(c_{2}\lor\neg c_{3})\land(c_{3}\lor\neg
c_{1})\end{array}$ (1)

Under the truth assignment $\sigma$ = $\\{$$c_{1}$ = 1, $c_{2}$ = 1, $c_{3}$ =
1$\\}$, $C$ evaluates to true, i.e., $C_{i}$ = 1 for $i$ = 1, 2, 3. Thus, $n$*
= 3.

For $C$, we will generate another formula $D$, but in DNF, according to the
above discussion:

$\begin{array}[]{ll}D=D_{11}\lor D_{12}\lor D_{21}\lor D_{22}\lor D_{31}\lor
D_{32}\\\ \hskip 11.38092pt=(c_{1}\land c_{4})\lor(c_{2}\land\neg
c_{4})\lor\\\ \hskip 21.76633pt(c_{2}\land c_{5})\lor(\neg c_{3}\land\neg
c_{5})\lor\\\ \hskip 21.76633pt(c_{3}\land c_{6})\lor(\neg c_{1}\land\neg
c_{6}).\end{array}$ (2)

According to Proposition 1, $D$ should also have at least $n$* = 3
conjunctions which evaluates to true under some truth assignment. In the
opposite, if $D$ has at least 3 satisfied conjunctions under a truth
assignment, then $C$ should have at least three clauses satisfied by some
truth assignment, too. In fact, it can be seen that under the truth assignment
$\tilde{\sigma}$ = $\\{$$c_{1}$ = 1, $c_{2}$ = 1, $c_{3}$ = 1, $c_{4}$ = 1,
$c_{5}$ = 1, $c_{6}$ = 1$\\}$, $D$ has three satisfied conjunctions: $D_{11}$,
$D_{21}$, and $D_{31}$, from which the three satisfied clauses in $C$ can be
immediately determined.

In the following, we will discuss a polynomial time algorithm to find a
maximum set of satisfied conjunctions in any logic formular in DNF, not only
restricted to the case that each conjunction contains up to 2 conjuncts.

##  III Algorithm description

In this section, we discuss our algorithm. First, we present the main idea in
Section III-A. Then, in Section III-B, a basic algorithm for solving the
problem will be described in great detail. The further improvement of the
basic algorithm will be discussed in the next section.

###  III-A Main idea

To develop an efficient algorithm to find a truth assignment that maximizes
the number of satisfied conjunctions in formula $D$ = $D_{1}$ $\lor$ …, $\lor$
$D_{n}$, where each $D_{i}$ ($i$ = 1, …, $n$) is a conjunction of variables
$c$ ($\in$ $V$), we need to represent each $D_{i}$ as a variable sequence. For
this purpose, we introduce a new notation:

($c_{j}$, *) = $c_{j}$ $\lor$ $\neg$$c_{j}$ = true,

which will be inserted into $D_{i}$ to represent any missing variable $c_{j}$
$\in$ $D_{i}$ (i.e., $c_{j}$ $\in$ $V$, but not appearing in $D_{i}$).
Obviously, the truth value of each $D_{i}$ remains unchanged.

In this way, the above $D$ can be rewritten as a new formula in DNF as
follows:

$\begin{array}[]{ll}D=D_{1}\lor D_{2}\lor D_{3}\lor D_{4}\lor D_{5}\lor
D_{6}\\\ \hskip 11.38092pt=(c_{1}\land(c_{2},*)\land(c_{3},*)\land
c_{4}\land(c_{5},*)\land(c_{6},*))\lor\\\ \hskip 21.76633pt((c_{1},*)\land
c_{2}\land(c_{3},*)\land\neg c_{4}\land(c_{5},*)\land(c_{6},*))\lor\\\ \hskip
21.76633pt((c_{1},*)\land c_{2}\land(c_{3},*)\land(c_{4},*)\land
c_{5}\land(c_{6},*))\lor&\\\ \hskip
21.76633pt((c_{1},*)\land(c_{2},*)\land\neg c_{3}\land(c_{4},*)\land\neg
c_{5}\land(c_{6},*))\lor\\\ \hskip 21.76633pt((c_{1},*)\land(c_{2},*)\land
c_{3}\land(c_{4},*)\land(c_{5},*)\land c_{6})\lor\\\ \hskip 21.76633pt(\neg
c_{1}\land(c_{2},*)\land(c_{3},*)\land(c_{4},*)\land(c_{5},*)\land\neg
c_{6})\end{array}$ (3)

Doing this enables us to represent each $D_{i}$ as a variable sequence, but
with all the negative literals being removed. It is because if the variable in
a negative literal is set to true, the corresponding conjunction must be
false. See Table I for illustration.

TABLE I: Conjunctions represented as sorted variable sequences with start symbol $\\#$ and end symbol $\$$ being used as sentinels. conjunction | variable sequences | sorted variable sequences
---|---|---
$D_{1}$ |  $c_{1}$.($c_{2}$, *).($c_{3}$, *).$c_{4}$.$(c_{5},*)$.($c_{6}$, *) |  $\\#.$($c_{2}$, *).($c_{3}$, *).$c_{1}$.$c_{4}$.$(c_{5},*)$.($c_{6}$, *).$\$$
$D_{2}$ | ($c_{1}$, *).$c_{2}$.($c_{3}$, *).($c_{5}$, *).($c_{6}$, *) |  $\\#.$$c_{2}$.($c_{3}$, *).($c_{1}$, *).($c_{5}$, *).($c_{6}$, *).$\$$
$D_{3}$ | ($c_{1}$, *).$c_{2}$.($c_{3}$, *).($c_{4}$, *).$c_{5}$.($c_{6}$, *) |  $\\#.$$c_{2}$.($c_{3}$, *).($c_{1}$, *).($c_{4}$, *).$c_{5}$.($c_{6}$, *).$\$$
$D_{4}$ | ($c_{1}$, *).($c_{2}$, *).($c_{4}$, *).($c_{6}$, *) |  $\\#.$($c_{2}$, *).($c_{1}$, *).($c_{4}$, *).($c_{6}$, *).$\$$
$D_{5}$ | ($c_{1}$, *).($c_{2}$, *).$c_{3}$.($c_{4}$, *).($c_{5}$, *).$c_{6}$ |  $\\#.$($c_{2}$, *).$c_{3}$.($c_{1}$, *).($c_{4}$, *).($c_{5}$, *).$c_{6}$.$\$$
$D_{6}$ | ($c_{2}$, *).($c_{3}$, *).($c_{4}$, *).($c_{5}$, *) |  $\\#.$($c_{2}$, *).($c_{3}$, *).($c_{4}$, *).($c_{5}$, *).$\$$

First, we pay attention to the variable sequence for $D_{2}$ (the second
sequence in the second column of Table I), in which the negative literal
$\neg$$c_{4}$ (in $D_{2}$) is elimilated. In the same way, you can check all
the other variable sequences.

Now it is easy for us to compute the appearance frequencies of different
variables in the variable sequences, by which each ($c$, *) is counted as a
single appearance of $c$ while any negative literals are not considered, as
illustrated in Table II, in which we show the appearance frequencies of all
the variables in the above $D$.

TABLE II: Appearance frequencies of variables. variables | $c_{1}$ | $c_{2}$ | $c_{3}$ | $c_{4}$ | $c_{5}$ | $c_{6}$
---|---|---|---|---|---|---
appearance frequencies | 5/6 | 6/6 | 5/6 | 5/6 | 5/6 | 5/6

According to the variable appearance frequencies, we will impose a global
ordering over all variables in $D$ such that the most frequent variables
appear first, but with ties broken arbitrarily. For instance, for the $D$
shown above, we can specify a global ordering like this: $c_{2}$ $\to$ $c_{3}$
$\to$ $c_{1}$ $\to$ $c_{4}$ $\to$ $c_{5}$ $\to$ $c_{6}$.

Following this general ordering, each conjunction $D_{i}$ in $D$ can be
represented as a sorted variable sequense as illustrated in the third column
of Table I, where the variables in a sequence are ordered in terms of their
appearance frequencies such that more frequent variables appear before less
frequent ones. In addition, a start symbol $\\#$ and an end symbol $\$$ are
used as sentinels for technical convenience. In fact, any global ordering of
variables works well (i.e., you can specify any global ordering of variables),
based on which a graph representation of assignments can be established.
However, ordering variables according to their appearance frequencies can
greatly improve the efficiency when searching the trie (to be defined in the
next subsection) constructed over all the variable sequences for conjunctions
in $D$.

Later on, by a variable sequence, we always mean a sorted variable sequence.
Also, we will use $D_{i}$ and the variable sequence for $D_{i}$
interchangeably without causing any confusion.

In addition, for our algorithm, we need to introduce a graph structure to
represent all those truth assignments for each $D_{i}$ ($i$ = 1, …, $n$)
(called a $p$*-graph), under which $D_{i}$ evaluates to true. In the
following, however, we first define a simple concept of $p$-graphs for ease of
explanation.

Definition 1. ($p$-graph) Let $\alpha$ $=$ $c_{0}$$c_{1}$ … $c_{k}$$c_{k+1}$
be an variable sequence representing a $D_{i}$ in $D$ as described above (with
$c_{0}$ $=$ $\\#$ and $c_{k+1}$ $=$ $\$$). A $p$-graph over $\alpha$ is a
directed graph, in which there is a node for each $c_{j}$ ($j$ $=$ $0$, …, $k$
$+$ $1$); and an edge for ($c_{j}$, $c_{j+1}$) for each $j$ $\in$ $\\{$$0$,
$1$, …, $k$$\\}$. In addition, there may be an edge from $c_{j}$ to $c_{j+2}$
for each $j$ $\in$ $\\{$$0$, …, $k$ \- $1$$\\}$ if $c_{j+1}$ is a pair of the
form ($c$, *), where $c$ is a variable name.

In Fig. 1(a), we show such a $p$-graph for $D_{1}$ = $\\#.$($c_{2}$,
*).($c_{3}$, *).$c_{1}$.$c_{4}$.($c_{5}$, *).($c_{6}$, *).$\$$. Beside a main
path $p$ going from $\\#$ to $\$$, and through all the variables in $D_{1}$,
there are four off-path edges (edges not on the main path), referred to as
$spans$ attached to $p$, corresponding to ($c_{2}$, *), ($c_{3}$, *),
($c_{5}$, *), and ($c_{6}$, *), respectively. Each span is represented by the
subpath covered by it. For example, we will use the subpath $<$$v_{0}$,
$v_{1}$, $v_{2}$$>$ (subpath going three nodes: $v_{0}$, $v_{1}$, $v_{2}$) to
stand for the span connecting $v_{0}$ and $v_{2}$; $<$$v_{1}$, $v_{2}$,
$v_{3}$$>$ for the span connecting $v_{2}$ and $v_{3}$; $<$$v_{4}$, $v_{5}$,
$v_{6}$$>$ for the span connecting $v_{4}$ and $v_{6}$, and $<$$v_{5}$,
$v_{6}$, $v_{7}$$>$ for the span connecting $v_{6}$ and $v_{7}$. By using
spans, the meaning of ‘*’s (it is either 0 or 1) is appropriately represented
since along a span we can bypass the corresponding variable (then its value is
set to 0) while along an edge on the main path we go through the corresponding
variable (then its value is set to 1).

Figure 1: A $p$-path and a $p*$-path.

In fact, what we want is to represent all those truth assignments for each
$D_{i}$ ($i$ = 1, …, $n$) in an efficient way, under which $D_{i}$ evaluates
to true. However, $p$-graphs fail to do so since when we go through from a
node $v$ to another node $u$ through a span, $u$ must be selected. If $u$
represents a ($c$, *) for some variable name $c$, the meaning of this ‘*’ is
not properly rendered. It is because ($c$, *) indicates that $c$ is optional,
but going through a span from $v$ to ($c$, *) makes $c$ always selected. So,
the intention of ($c$, *) is not well implemented.

For this reason, we introduce the concept of $p$*-graphs, described as below.

Let $s_{1}$ = $<$$v_{1}$, …, $v_{k}$$>$ and $s_{2}$ = $<$$u_{1}$, …,
$u_{l}$$>$ be two spans attached on a same path. We say, $s_{1}$ and $s_{2}$
are overlapped, if $u_{1}$ = $v_{j}$ for some $j$ $\in$ $\\{$1, …, $k$ \-
1$\\}$, or if $v_{1}$ = $u_{j^{\prime}}$ for some $j^{\prime}$ $\in$ $\\{$1,
…, $l$ \- 1$\\}$. For example, in Fig. 1(a), $<$$v_{0}$, $v_{1}$, $v_{2}$$>$
and $<$$v_{1}$, $v_{2}$, $v_{3}$$>$ are overlapped. $<$$v_{4}$ $v_{5}$,
$v_{6}$$>$ and $<$$v_{5}$, $v_{6}$, $v_{7}$$>$ are also overlapped.

Here, we notice that if we had one more span, $<$$v_{3}$, $v_{4}$, $v_{5}$$>$,
for example, it would be connected to $<$$v_{1}$, $v_{2}$, $v_{3}$$>$, but not
overlapped with $<$$v_{1}$, $v_{2}$, $v_{3}$$>$. Being aware of this
difference is important since the overlapped spans imply the consecutive ‘*’s,
just like $<$$v_{1}$, $v_{1}$, $v_{2}$$>$ and $<$$v_{1}$, $v_{2}$, $v_{3}$$>$,
which correspond to two consecutive ‘*’s: ($c_{2}$, *) and ($c_{3}$, *).
Therefore, the overlapped spans exhibit some kind of transitivity. That is, if
$s_{1}$ and $s_{2}$ are two overlapped spans, the $s_{1}$ $\cup$ $s_{2}$ must
be a new, but bigger span. Applying this operation to all the spans over a
$p$-path, we will get a ’transitive closure’ of overlapped spans. Based on
this observation, we give the following definition.

Definition 2. ($p$*-graph) Let $P$ be a $p$-graph. Let $p$ be its main path
and $S$ be the set of all spans over $p$. Denote by $S$* the ‘transitive
closure’ of $S$. Then, the $p$*-graph with respect to $P$ is the union of $p$
and $S$*, denoted as $P$* $=$ $p$ $\cup$ $S$*.

In Fig. 1(b), we show the $p$*-graph with respect to the $p$-graph shown in
Fig. 1(a). Concerning $p$*-graphs, we have the following lemma.

######  Lemma 1.

Let $P$* be a $p$*-graph for a conjunction $D_{i}$ (represented as a variable
sequence) in $D$. Then, each path from $\\#$ to $\$$ in $P$* represents a
truth assignment, under which $D_{i}$ evaluate to true.

###### Proof.

(1) Corresponding to any truth assignment $\sigma$, under which $D_{i}$
evaluates to $true$, there is definitely a path from $\\#$ to $\$$ in
$p$*-path. First, we note that under such a truth assignment each variable in
a positive literal must be set to 1, but with some ‘*’s set to 1 or 0.
Especially, we may have more than one consecutive ‘*’s that are set 0, which
are represented by a span that is the union of the corresponding overlapped
spans. Therefore, for $\sigma$ we must have a path representing it.

(2) Each path from $\\#$ to $\$$ represents a truth assignment, under which
$D_{i}$ evaluate to true. To see this, we observe that each path consists of
several edges on the main path and several spans. Especially, any such path
must go through every variable in a positive literal since for each of them
there is no span covering it. But each span stands for a ‘*’ or more than one
successive ‘*’s. ∎

###  III-B Basic algorithm

To find a truth assignment to maximize the number of satisfied
$D_{j}^{\prime}$s in $D$, we will first construct a trie-like structure $G$
over $D$, and then search $G$ bottom-up to find answers.

Let $P_{1}$*, $P_{2}$*, …, $P_{n}$* be all the $p$*-graphs constructed for all
$D_{j}$’s in $D$, respectively. Let $p_{j}$ and $S_{j}$* ($j$ = 1, …, $n$) be
the main path of $P_{j}$* and the transitive closure over its spans,
respectively. We will construct $G$ in two steps. In the first step, we will
establish a trie [13], denoted as $T$ = $trie$($R$) over $R$ = $\\{$$p_{1}$,
…, $p_{n}$$\\}$ as follows.

If $|R|$ = 0, $trie$($R$) is, of course, empty. For $|R|$ = 1, $trie$($R$) is
a single node. If $|R|$ $>$ 1, $R$ is split into $m$ (possibly empty) subsets
$R_{1}$, $R_{2}$, …, $R_{m}$ so that each $R_{i}$ ($i$ = 1, …, $m$) contains
all those sequences with the same first variable name. The tries:
$trie(R_{1}$), $trie(R_{2}$), …, $trie(R_{m}$) are constructed in the same way
except that at the $k$th step, the splitting of sets is based on the $k$th
variable name (along the global ordering of variables). They are then
connected from their respective roots to a single node to create $trie$($R$).

In Fig. 2, we show the trie constructed for the variable sequences shown in
the third column of Table I. In such a trie, special attention should be paid
to all the leaf nodes each labeled with $\$$, representing a conjunction (or a
subset of conjunctions, which can be satisfied under the truth assignment
represented by the corresponding main path.)

The advantage of tries is to cluster common parts of variable sequences
together to avoid possible repeated checking. (Then, this is the main reason
why we sort variable sequences according to their appearance frequencies.)
Especially, this idea can also be applied to the variable subsequences (as
will be seen in Section IV-B), over which some dynamical tries can be
recursively constructed, leading to a polynomial time algorithm for solving
the problem.

Each edge in the trie is referred to as a tree edge. In addition, the variable
$c$ associated with a node $v$ is referred to as the label of $v$, denoted as
$l$($v$) = $c$. Also, we will associate each node $v$ in the trie $T$ a pair
of numbers (pre, post) to speed up recognizing ancestor/descendant
relationships of nodes in $T$, where pre is the order number of $v$ when
searching $T$ in preorder and post is the order number of $v$ when searching
$T$ in postorder.

Figure 2: A trie and tree encoding.

These two numbers can be used to characterize the ancestor-descendant
relationships in $T$ as follows.

  * -

Let $v$ and $v\textquoteright$ be two nodes in $T$. Then, $v\textquoteright$
is a descendant of $v$ iff pre($v\textquoteright$) > pre($v$) and
post($v\textquoteright$) < post($v$).

For the proof of this property of any tree, see Exercise 2.3.2-20 in [12].

For instance, by checking the label associated with $v_{2}$ against the label
for $v_{9}$ in Fig. 2, we see that $v_{2}$ is an ancestor of $v_{9}$ in terms
of this property. We note that $v_{2}$’s label is (3, 12) and $v_{9}$’s label
is (10, 6), and we have 3 < 10 and 12 > 6\. We also see that since the pairs
associated with $v_{14}$ and $v_{6}$ do not satisfy the property, $v_{14}$
must not be an ancestor of $v_{6}$ and vice versa.

In the second step, we will add all $S_{i}$* ($i$ = 1, …, $n$) to the trie $T$
to construct a trie-like graph $G$, as illustrated in Fig. 3. This trie-like
graph is constructed for all the variable sequences given in Table I, in which
each span is associated with a set of numbers used to indicate what variable
sequences the span belongs to. For example, the span $<$$v_{0}$, $v_{1}$,
$v_{2}$$>$ (in Fig. 3) is associated with three numbers: 1, 5, 6, indicating
that the span belongs to 3 conjunctions: $D_{1}$, $D_{5}$, and $D_{6}$. But no
numbers are associated with any tree edges.

In addition, each $p$*-graph itself is considered to be a simple trie-like
graph.

From Fig. 3, we can see that although the number of truth assignments for $D$
is exponential, they can be represented by a graph with polynomial numbers of
nodes and edges. In fact, in a single $p$*-graph, the number of edges is
bounded by O($n^{2}$). Thus, a trie-like graph over $m$ $p$*-graphs has at
most O($n^{2}m$) edges.

Figure 3: A trie-like graph $G$.

In a next step, to find the answer, we will search $G$ bottom-up level by
level. First of all, for each leaf node, we will figure out all its parents.
Then, all such parent nodes will be categorized into different groups such
that the nodes in the same group will have the same label (variable name),
which enables us to recognizes all those conjunctions which can be satisfied
by a same assignment efficiently. All the groups containing only a single node
will not be further explored. (That is, if a group contains only one node $v$,
the parent of $v$ will not be checked.) Next, all the nodes with more than one
node will be explored. We repeat this process until we reach a level at which
each group contains only one node. In this way, we will find a set of
subgraphs, each rooted at a certain node $v$, in which the nodes at the same
level must be labeled with the same variable name. Then, the path in the trie
from the $root$ to $v$ and any path from $v$ to a leaf node in the subgraph
correspond to an assignment satisfying all the conjunctions labeling a leaf
node in it.

See Fig. 4 for illustration.

In Fig. 4, we show part of the bottom-up process of searching the trie-like
graph $G$ shown in Fig. 3.

Figure 4: Illustration for the layered representation $G^{\prime}$ of $G$.

  * •

step 1: The leaf nodes of $G$ are $v_{7}$, $v_{10}$, $v_{13}$, $v_{17}$ (see
level 1), representing the 6 variable sequences in $D$ shown in Table I,
respectively. (Especially, node $v_{7}$ alone represents three of them:
$D_{1}$, $D_{3}$, $D_{5}$.) Their parents are all the remaining nodes in $G$
(see level 2 in Fig. 4). Among them, $v_{6}$, $v_{9}$, $v_{16}$ are all
labeled with the same variable name ‘$c_{6}$’ and will be put in a group
$g_{1}$. The nodes $v_{5}$, $v_{8}$, and $v_{15}$ are labeled with ‘$c_{5}$’
and will be put in a second group $g_{2}$. The nodes $v_{4}$, $v_{11}$, and
$v_{15}$ are labeled with ‘$c_{4}$’ and will be put in the third group
$g_{3}$. Finally, the nodes $v_{3}$ and $v_{14}$ are labeled with ‘$c_{1}$’
and are put in group $g_{4}$. All the other nodes: $v_{0}$, $v_{1}$, $v_{2}$
each are differently labeled and therefore will not be further explored.

  * •

step 2: The parents of the nodes in all groups $g_{1}$, $g_{2}$, $g_{3}$, and
$g_{4}$ will be explored. We first check $g_{1}$. The parents of the nodes in
$g_{1}$ are shown at level 3 in Fig. 4. Among them, the nodes $v_{5}$ and
$v_{8}$ are labeled with ‘$c_{5}$’ and will be put in a same group $g_{11}$;
the nodes $v_{4}$ and $v_{15}$ are labeled with ‘$c_{4}$’ and put in another
group $g_{12}$; the nodes $v_{3}$ and $v_{14}$ are labeled with ‘$c_{1}$’ and
put in group $g_{13}$. Again, all the remaining nodes are differently labeled
and will not be further considered. The parents of $g_{2}$, $g_{3}$, and
$g_{4}$ will be handled in a similar way.

  * •

step 3: The parents of the nodes in $g_{11}$, $g_{12}$, $g_{13}$, as well as
the parents of the the nodes in any other group whose size is larger than 1
will be checked. The parents of the nodes in $g_{11}$ are $v_{2}$, $v_{3}$,
and $v_{4}$. They are differently labeled and will not be further explored.
However, among the parents of the nodes in group $g_{12}$, $v_{4}$ and
$v_{15}$ are labeled with ‘$c_{1}$’ and will be put in a group $g_{121}$. The
parents of the nodes in $g_{13}$ are also differently labeled and will not be
searched. Again, the parents of all the other groups at level 3 in Fig. 4 will
be checked similarly.

  * •

step 4: The parents of the nodes in $g_{121}$ and in any other groups at level
4 in Fig. 4 will be explored. Since the parents of the nodes in $g_{121}$ are
differently labeled the whole working process terminates if the parents of the
nodes in any other other groups at this level are also differently labeled.

We call the graph illustrated in Fig. 4 a layered representation $G^{\prime}$
of $G$. From this, a maximum subset of conjunctions satisfied by a certain
truth assignment represented by a subset of variables that are set to 1 (while
all the remaining variables are set to 0) can be efficiently calculated. As
mentioned above, each node which is the unique node in a group will have no
parents. We refer to such a node as a s-root, and the subgraph made up of all
nodes reachable from the s-root as a rooted subgraph. For example, the
subgraph made up of the blackened nodes in Fig. 4 is one of such subgraphs.

Denote a rooted subgraph rooted at node $v$ by $G_{v}$. In $G_{v}$, the path
labels from $v$ to a leaf node are all the same. Then, any conjunction $D_{i}$
associated with a leaf node $u$ is satisfied by a same truth assignment
$\sigma$:

$\sigma$ = $\\{$the lables on the path $P$ from $v$ to $u$$\\}$ $\cup$
$\\{$the labels

on the path from the the root of the whole trie to $v$$\\}$,

if any edge on $P$ is a tree edge or the set of numbers assiciated with it
contains $i$. We call this condition the assignment condition.

For instance, in the rooted subgraph mentioned above (represented by the
blackened nodes in Fig. 4), we have two root-to-leaf paths: $v_{1}$
$\xrightarrow{6}$ $v_{11}$ $\xrightarrow{6}$ $v_{13}$, $v_{1}$
$\xrightarrow{4}$ $v_{15}$ $\xrightarrow{4}$ $v_{17}$, with the same path
label; and both satisfy the assignment condition. Then, this rooted subgraph
represents a subset: $\\{$$D_{4}$, $c_{6}$$\\}$, which are satisfied by a
truth assignment: $\\{$$c_{2}$, $c_{4}$$\\}$ $\cup$ $\\{$$c_{2}$$\\}$ =
$\\{$$c_{2}$, $c_{4}$$\\}$ (i.e., $\\{$$c_{2}$ = 1, $c_{4}$ = 1, $c_{1}$ = 0,
$c_{3}$ = 0, $c_{5}$ = 0, $c_{6}$ = 0$\\}$)

Now we consider the node $v_{4}$ at level 4 in Fig. 4. The rooted subgraph
rooted at it contains only one path $v_{4}$ $\rightarrow$ $v_{5}$
$\rightarrow$ $v_{6}$, where each edge is a tree edge and $v_{6}$ represents
$\\{$$D_{1}$, $D_{3}$, $c_{5}$$\\}$. This path corresponds to a truth
assignment $\sigma$ = $\\{$$c_{4}$, $c_{5}$, $c_{6}$$\\}$ $\cup$ $\\{$$c_{1}$,
$c_{2}$, $c_{3}$$\\}$ = $\\{$$c_{1}$, $c_{2}$, $c_{3}$, $c_{4}$, $c_{5}$,
$c_{6}$$\\}$ (i.e., $\sigma$ = $\\{$ $c_{1}$ = 1, $c_{2}$ = 1, $c_{3}$ = 1,
$c_{4}$ = 1, $c_{5}$ = 1, $c_{6}$ = 1$\\}$), showing that under $\sigma$:
$D_{1}$, $D_{3}$, $D_{5}$ evaluate to true, which are in fact a maximum subset
of satisfied conjunctions in $D$. From this, we can deduce that in the formula
$C$ we must also have a maximum set of three satisfied clauses. Also,
according to $\sigma$, we can quickly find those three satisfied clauses in
$C$.

In terms of the above discussion, we give the following algorithm. In the
algorithm, a $stack$ $S$ is used to explore $G$ to form the layered graph
$G^{\prime}$. In $S$, each entry is a subset of nodes labeled with a same
variable name. Initially, $S$ = $\emptyset$.

Input : a trie-like graph $G$.

Output : a largest subset of conjunctions satisfying a certain truth
assignment.

1 $G^{\prime}$ :=$\\{$all leaf nodes of $G$$\\}$; $g$ := $\\{$all leaf nodes
of $G$$\\}$;

2 push($S$, $g$); (* find the layered graph $G^{\prime}$ of $G$ *)

3 while  _$S$ is not $empty$_ do

4 $g$ := pop($S$);

5 find the parents of each node in $g$; add them to $G^{\prime}$;

6 divide all such parent nodes into several groups: $g_{1}$, $g_{2}$, …,
$g_{k}$ such that all the nodes in a group with the same label;

7 for  _each $j$ $\in$ $\\{$$1$, …, $k$$\\}$_ do

8 if  _$|g_{j}|$ $>$ $1$_ then

9 push($S$, $g_{j}$);

10

11

12

return $findSubset$($G^{\prime}$);

Algorithm 1 SEARCH($G$)

Input : a layered graph $G^{\prime}$.

Output : a largest subset of conjunctions satisfying a certain truth
assignment.

1

2($u$, $s$, $f$) := ($null$, 0, $\emptyset$); (* find a truth assignment
satisfying a maximum subset of conjunctions. $\emptyset$ represents an $empty$
set.*)

3 for  _each rooted subgraph $G_{v}$_ do

4 determine the subset $D^{\prime}$ of satisfied conjunctions in $G_{v}$;

5 if  _$|D^{\prime}|$ $>$ $s$_ then

6 $u$ := $v$; $s$ := $|D^{\prime}|$; $f$ := $D^{\prime}$;

7

return ($u$, $s$, $f$);

Algorithm 2 findSubset($G^{\prime}$)

The algorithm can be divided into two parts. In the first part (lines 2 - 12),
we will find the layered representation $G^{\prime}$ of $G$. In the second
part (line 13), we call subprocedure findSubset( ), by which we check all the
rooted subgraphs to find a truth assignment such that the satisfied
conjunctions are maximized. This is represented by a triplet ($u$, $s$, $f$),
corresponding to a rooted subgraph $G_{u}$ rooted at $u$ in $G^{\prime}$.
Then, the variable names represented by the path from the root of the whole
trie to $u$ and the variable names represented by any path in $G^{\prime}$
make up a truth assignment that satisfies a largest subset of conjunctions
stored in $f$, whose size is $s$.

Concerning the correctness of the algorithm, we have the following
proposition.

######  Proposition 2.

Let $D$ be a formula in DNF. Let $G$ be a trie-like graph created for $D$.
Then, the result produced by $SEARCH$($G$) must be a truth assignment
satisfying a maximum subset of conjunctions in $D$.

###### Proof.

By the execution of $SEARCH$($G$), we will first generate the layered
reprentation $G^{\prime}$ of $G$. Then, all the rooted subgraphs in
$G^{\prime}$ will be checked. By each of them, we will find a truth assignment
satisfying a subset of conjunctions, which will be compared with the largest
subset of conjunctions found up to now. Only the larger between them is kept.
Therefore, the result produced by $SEARCH$($G$) must be correct. ∎

##  IV Improvements

###  IV-A Redundancy analysis

The working process of constructing the layered representation $G^{\prime}$ of
$G$ does a lot of redundant work, but can be effectively removed by
interleaving the process of SEARCH and findSubset in some way. We will
recognize any rooted subgraph as early as possible, and remove the relevant
nodes to avoid any possible redundancy. To see this, let us have a look at
Fig. 5, in which we illustrate part of a possible layered graph, and assume
that from group $g_{1}$ we generate another two groups $g_{2}$ and $g_{3}$.
From them a same node $v_{3}$ will be accessed. This shows that the number of
the nodes at a layer in $G^{\prime}$ can be larger than O($nm$) (since a node
may appear more than once.)

Fortunately, such kind of repeated appearance of a node can be avoided by
applying the findSubset procedure multiple times during the execution of
SEARCH( ) with each time applied to a subgraph of $G^{\prime}$, which
represents a certain truth assignment satisfying a subset of conjunctions that
cannot be involved in any larger subset of satisfiable conjunctions.

For this purpose, we need first to recognize what kinds of subgraphs in a
trie-like graph $G$ will lead to the repeated appearances of a node at a layer
in $G^{\prime}$.

In general, we distingush among three cases, by which we assume two nodes $u$
and $v$ respectively appearing in $g_{2}$ and $g_{3}$ (in Fig. 5), with
$v_{3}$ $\rightarrow$ $u$, $v_{3}$ $\rightarrow$ $v$ $\in$ $G$.

Figure 5: A possible part in a layered graph $G^{\prime}$. Figure 6: Two
reasons for repeated appearances of nodes at a level in $G^{\prime}$.

  * •

Case 1: $u$ and $v$ appear on different paths in $G$, as illustrated in Fig.
6(a)), in which nodes $v_{1}$ and $v_{2}$ are differently labelled. Thus, when
we create the corresponding layered representation, they will belong to
different groups, as shown in Fig. 6(b), matching the pattern shown in Fig. 5.

  * •

Case 2: $u$ and $v$ appear on a same path in $G$, as illustrated in Fig.
6(c)), in which two nodes $v_{1}$ and $v_{2}$ appear on a same path (and then
must be differently labelled.) Hence, when we create the corresponding layered
representation, they definitely belong to different groups, as illustrated in
Fig. 6(d), also matching the pattern shown in Fig. 5.

  * •

Case 3: The combination of Case 1 and Case 2. To know what it means, assume
that in $g_{1}$ (in Fig. 5) we have two nodes $u$ and $u^{\prime}$ with $u$
$\rightarrow$ $v_{3}$ and $u^{\prime}$ $\rightarrow$ $v_{3}$. Thus, if $u$ and
$v$ appear on different paths, but $u^{\prime}$ and $v$ on a same path in $T$,
then we have Case 3, by which Case 1 and Case 2 occur simuteneously by a
repeated node at a certain layer in $G^{\prime}$.

Case 1 and Case 2 can be efficiently differentiated from each other by using
the tree encoding, as illuatrated in Fig. 2.

In Case 1 (as illustrate in Fig. 6(a) and (b)), a node $v$ which appears more
than once at a level in $G^{\prime}$ must be a branching node (i.e., a node
with more than one child) in $T$. Thus, each subset of conjunctions
represented by all those substrees repectively rooted at the same-labelled
children of $v$ must be a largest subset of conjunctions that can be satisfied
by a truth assignment with $v$ (or say, the variable represented by $v$) being
set to true. Therefore, we can merge all the repeated nodes to a single one
and call findSubset( ) immediatly to find all such subsets for all the
children of $v$.

In Case 2 (as illustrated in Fig. 6(c) and (d)), some more effort should be
made. In this case, the multiple appearances of a node $v$ at a level in
$G^{\prime}$ correspond to more than one descendants of $v$ on a same path in
$T$: $v_{1}$, $v_{2}$, …, $v_{k}$ for some $k$ > 1\. (As demonstrated in Fig.
6(c), both $v_{1}$ and $v_{2}$ are $v_{3}$’s descendants.) Without loss of
generality, assume that $v_{1}$ $\Leftarrow$ $v_{2}$ $\Leftarrow$ …
$\Leftarrow$ $v_{k}$, where $v_{i}$ $\Leftarrow$ $v_{i+1}$ represents that
$v_{i}$ is a descendant of $v_{i+1}$ (1 $\leq$ $i$ $\leq$ $k$ \- 1).

In this case, we will merge the multiple appearances of $v$ to a single
appearance of $v$ and connect $v_{k}$ to $v$. Any other $v_{i}$ ($i$ $\in$
$\\{$1, 2, …, $k$\- 1$\\}$) will be simply connected to $v$ if the following
condition is satisfied.

  1. -

$v_{i}$ appears in a group which contains at least another node $u$ such that
$u^{\prime}$s parent is diffrent from $v$, but with the same label as $v$.

Otherwise, $v_{i}$ ($i$ $\in$ $\\{$1, 2, …, $k$\- 1$\\}$) will not be
connected to $v$. It is because if the condition is not met the truth
assignment represented by the path in $G$, which contains the span ($v$,
$v_{i}$), cannot satisfy any two or more conjunctions. But the single
satisfied conjunction is already figured out when we create the trie at the
very beginning. However, we should know that this checking is only for
efficiency. Whether doing this or not will not impact the correctness of the
algorithm or the worst-case running time analysis.

Based on Case 1 and Case 2, Case 3 is easy to handle. We only need to check
all the children of the repeated nodes and carefully distinguish between Case
1 and Case 2 and handle them differently.

See Fig. 4 and 7 for illustration.

First, we pay attention to $g_{1}$ and $g_{2}$ at level 2 in Fig. 4,
especially nodes $v_{6}$ and $v_{9}$ in $g_{1}$, and $v_{8}$ in $g_{2}$, which
match the pattern shown in Fig. 5. As we can see, $v_{6}$ and $v_{8}$ are on
different paths in $T$ and then we have Case 1. But $v_{9}$ and $v_{8}$ are on
a same path, which is Case 2. To handle Case 1, we will search along two paths
in $G^{\prime}$: $v_{3}$ $\xrightarrow{1,5}$ $v_{6}$ $\rightarrow$ $v_{7}$
(labeled with $\\{$$D_{1}$, $D_{3}$, $D_{5}$$\\}$), $v_{3}$ $\rightarrow$
$v_{8}$ $\rightarrow$ $v_{10}$ (labeled with $\\{$$D_{2}$$\\}$), and find a
subset of three conjunctions $\\{$$D_{1}$, $D_{5}$, $D_{2}$$\\}$, satisfied by
a truth assignment: $\\{$$c_{1}$ = 1, $c_{2}$ = 1, $c_{3}$ = 1, $c_{4}$ = 0,
$c_{5}$ = 0, $c_{6}$ = 1$\\}$. To handle Case 2, we simply connect $v_{8}$ to
the first appearance of $v_{3}$ as illustrated in Fig. 7 and then eliminate
second appearance of $v_{3}$ from $G^{\prime}$.

Figure 7: Illustration for removing repeated nodes.

###  IV-B Improved algorithm

In terms of the above discussion, the method to generate $G^{\prime}$ should
be changed. We will now generate $G^{\prime}$ level by level. After a level is
created, the repeated appearances of nodes will be checked and then
eliminated. In this way, the number of nodes at each layer can be kept $\leq$
O($nm$).

However, to facilitate the recognition of truth assignments for the
corresponding satisfied conjunctions, we need a new concept, the so-called
reachable subsets of a node $v$ through spans, denoted as $\textit{RS}_{v}$.

Definition 3. (reachable subsets through spans) Let $v$ be a repeated node of
Case 1. Let $u$ be a node on the tree path from root to $v$ in $G$ (not
including $v$ itself). A reachable subset of $u$ through spans are all those
nodes with a same label $c$ in different subgraphs in $G$[$v$] (subgraph
rooted at $v$) and reachable from $u$ through a span, denoted as
$\textit{RS}_{u}$[$c$].

For instance, for node $v_{2}$ in Fig. 3 (which is on the tree path from root
to $v_{3}$ (a repeated node of Case 1), we have two RSs:

  * -

$\textit{RS}_{v_{2}}$[$c_{5}$] = $\\{$$v_{5}$, $v_{8}$$\\}$,

  * -

$\textit{RS}_{v_{2}}$[$c_{6}$] = $\\{$$v_{6}$, $v_{9}$$\\}$.

We have $\textit{RS}_{v_{2}}$[$c_{5}$] due to two spans $v_{2}$
$\xrightarrow{5}$ $v_{5}$ and $v_{2}$ $\xrightarrow{2}$ $v_{8}$ going out of
$v_{2}$, respectively reaching $v_{5}$ and $v_{8}$ on two different
$p$*-graphs in $G$[$v_{3}$] with $l$($v_{5}$) = $l$($v_{8}$) = ‘$c_{5}$’. We
have $\textit{RS}_{v_{2}}$[$c_{6}$] due to another two spans going out of
$v_{2}$: $v_{2}$ $\xrightarrow{5}$ $v_{6}$ and $v_{2}$ $\xrightarrow{2}$
$v_{9}$ with $l$($v_{6}$) = $l$($v_{9}$) = ‘$c_{6}$’.

In general, we are interested only in $\textit{RS}_{v}$’s with
|$\textit{RS}_{v}$| $\geq$ 2\. So, in the subsequent discussion, by an
$\textit{RS}_{v}$, we mean an $\textit{RS}_{v}$ with |$\textit{RS}_{v}$|
$\geq$ 2.

The definition of this concept for a repeated node $v$ of Case 1 is a little
bit different from any other node on the tree path (from root to $v$).
Specifically, each of its RSs is defined to be a subset of nodes reachable
from a span or from a tree edge. So for $v_{3}$ we have:

  * -

$\textit{RS}_{v_{3}}$[$c_{5}$] = $\\{$$v_{5}$, $v_{8}$$\\}$,

  * -

$\textit{RS}_{v_{3}}$[$c_{6}$] = $\\{$$v_{6}$, $v_{9}$$\\}$,

respectively due to $v_{3}$ $\xrightarrow{5}$ $v_{5}$ and $v_{3}$
$\rightarrow$ $v_{8}$ going out of $v_{3}$ with $l$($v_{6}$) = $l$($v_{8}$) =
‘$c_{5}$’; and $v_{3}$ $\xrightarrow{5}$ $v_{6}$ and $v_{3}$ $\xrightarrow{2}$
$v_{9}$ going out of $v_{3}$ with $l$($v_{6}$) = $l$($v_{8}$) = ‘$c_{6}$’.

Based on the concept of reachable subsets through spans, we are able to define
another more important concept, upper boundaries, given below.

Definition 4. (upper boundaries) Let $v$ be a repeated node of Case 1. Let
$G_{1}$, $G_{2}$, …, $G_{k}$ be all the subgraphs rooted at a child of $v$ in
$G$. Let $RS_{v_{i}}$[$c_{j}$] ($i$ = 1, …, $l$; $j$ = 1, …, $q$ for some $l$,
$q$) be all the reachable subsets through spans. An upper boundary (denoted as
upBound) with respect to $v$ is a subset of nodes $\\{$$u_{1}$, $u_{2}$, …,
$u_{f}$$\\}$ with the following properties:

  1. 1.

Each $u_{i}$ (1 $\leq$ $i$ $\leq$ $l$) appears in some $G_{j}$ (1 $\leq$ $j$
$\leq$ $k$).

  2. 2.

For each pair $u_{i}$, $u_{j}$ ($i$ $\neq$ $j$) they are not related by the
ancestor/descendant relationship.

  3. 3.

Each $u_{i}$ ($i$ = 1, …, $l$) is in some $RS_{q}$[$c_{r}$]. But there is no
any other $RS_{q^{\prime}}$[$c_{r^{\prime}}$], containing a node at a higher
position than $u_{i}$ (or say, a node closer to the root than $u_{i}$) in the
same subgraph.

Fig. 8 gives an intuitive illustration of this concept.

Figure 8: Illustration for upBounds.

As a concrete example, consider $v_{5}$ and $v_{8}$ in Fig. 3. They make up an
upBound with respect to $v_{3}$ (repeated node of Case 1). Then, we will
construct a trie-like graph over two subgraphs, rooted at $v_{5}$ and $v_{8}$,
respectively. Then, we make a recursive call of the algorithm over such a
newly constructed trie-like subgraph to recognize some more subsets of
conjunctions which can be satisfied by a same truth assignment. Here, however,
$v_{4}$ is not included since the truth assignment with $v_{4}$ being set to
true satisfies only the conjunctions associated with leaf node $v_{10}$. This
has already been determined when the initial trie is built up. In fact, the
purpose of upper boundaries is to take away the nodes like $v_{4}$ from the
subsequent computation.

Specifically, the following operations will be carried out when encounteing a
repeated node $v$ of Case 1.

  * •

Calculate all RSs with respect $v$.

  * •

Calculate the upBound in terms of RSs.

  * •

Make a recursive call of the algorithm over all the $p$*-subgraphs each
starting from a node on the corresponding upBound.

  * •

Merge the repeated nodes of Case 1 to a single one at the corresponding layer
in $G^{\prime}$.

See the following example for illustration.

######  Example 1.

When checking the repeated node $v_{3}$ in the bottom-up search process, we
will calculate all the reachable subsets through spans with respect to $v_{3}$
as described above: $\textit{RS}_{v_{2}}$[$c_{5}$],
$\textit{RS}_{v_{2}}$[$c_{6}$], $\textit{RS}_{v_{3}}$[$c_{5}$], and
$\textit{RS}_{v_{3}}$[$c_{6}$]. In terms of these reachable subsets through
spans, we will get the corresponding upBound $\\{$$v_{5}$, $v_{8}$$\\}$. Node
$v_{4}$ (above the upBound) will not be involved by the recursive execution of
the algorithm.

Concretely, when we make a recursive call of the algorithm, applied to two
subgraphs: $G_{1}$ \- rooted at $v_{5}$, and $G_{2}$ \- rooted at $v_{8}$ (see
Fig. 9(a)), we will first constrcut a trie-like graph as shown in Fig. 9(b).
Here, we notice that the subset associated with its unique leaf node is
$\\{$$D_{2}$, $D_{5}$$\\}$, instead of $\\{$$D_{1}$, $D_{2}$, $D_{3}$,
$D_{5}$$\\}$. It is because the number associated with span $v_{2}$
$\xrightarrow{5}$ $v_{5}$ is 5 while the number associated with span $v_{2}$
$\xrightarrow{2}$ $v_{8}$ is 2.

Figure 9: Illustration for recursive call of the algorithm.

By searching the trie-like graph shown in Fig. 9(b), we will find the truth
assignment satisfying $\\{$$D_{2}$, $D_{5}$$\\}$. This truth assignment is
represented by a path consisting three parts: the tree path from root to
$v_{2}$, the span $v_{2}$ $\xrightarrow{5}$ $v_{5}$, the subpath $v_{5}$ to
$v_{7}$. So the truth assignment is $\\{$$c_{1}$ = 0, $c_{2}$ = 1, $c_{3}$ =
1, $c_{4}$ = 0, $c_{5}$ = 1, $c_{6}$ = 1$\\}$.

We remember that when generating the trie $T$ over the main paths of the
$p$*-graphs over the variable sequences shown in Table I, we have already
found a subset of conjunctions $\\{$$D_{1}$, $D_{3}$, $D_{5}$$\\}$, which can
be satisfied by a truth assignment represented by the corresponding main path.
This is larger than $\\{$$D_{2}$, $D_{5}$$\\}$. Therefore, $\\{$$D_{2}$,
$D_{5}$$\\}$ should not be kept around and this part of computation is futile.
However, this kind of useless work can be avoided by performing a pre-
checking: if the number of $p$*-subgraphs, over which the recursive call of
the algorithm will be invoked, is smaller than the size of the partial answer
already obtained, the recursive call of the algorithm should not be conducted.

In terms of the above discussion, we change SEARCH( ) to a recursive algorithm
shown below.

Input : a trie-like subgraphs $G$.

Output : a largest subset of conjunctions satisfying a certain truth
assignment.

1 assume that the height of $G$ is $m$;

2 let $L_{1}$ = $\\{$all the leaf nodes of $G$$\\}$;

3 for  _ $i$ = $1$ to $m$ \- $1$_ do

4 generate $L_{i+1}$ from $L_{i}$; (*each node in $L_{i+1}$ is a parent of
some nodes in $L_{i}$*)

5 for  _each repeated node $v$ in $L_{i+1}$_ do

6 Case 1: calculate RSs with respect to $v$ and the corresponding upBound; let
$D$ be the set of all the subgraphs each rooted at a node on upBound; generate
a trie-like subgraph $D^{\prime}$ over $D$; $D^{\prime}$ = $\\{$$v$$\\}$
$\cup$ $D^{\prime}$; call SEARCH($D^{\prime}$); Merge all the appearances of
$v$ to a single one;

7 Case 2: merge all the multiple appearances of $v$ to a single node;

8 Case 3: distinguish between the nodes of Case 1 and the nodes of Case 2; and
handle them differently;

9

10

11denote by $G^{\prime}$ the generated layered graph;

12 return $findSubset$($G^{\prime}$);

Algorithm 3 SEARCH($G$)

The improved algorithm (Algorithm 3) works in a quite different way from
Algorithm 1. Concretely, $G^{\prime}$ will be created level by level (see line
4), and for each created level all the multiple appearances of nodes $v$ will
be recognized and handled according to the three cases described in the
previous subsection (see lines 5 - 8). Especially, in Case 1, we will first
create the corresponding upBound $L$ with respect to $v$, and then generate a
trie-like graph $D^{\prime}$ over all those trie-like subgraphs each rooted at
a node on $L$. Next, $v$ will be added to $D^{\prime}$ as its root. Finally, a
recursive call to the algorithm on $D^{\prime}$ will be invoked.

In Case 2, all the repeated nodes will be simply merged together while in Case
3 the repeated nodes will be handled according to both Case 1 and Case 2.

Besides, $D^{\prime}$ = $\\{$$v$$\\}$ $\cup$ $D^{\prime}$ in line 6 is a
simplified representation of an operation, by which we add not only node $v$,
but also the corresponding edges to $D^{\prime}$.

The sample trace given in the following example helps for illustration.

######  Example 2.

When applying SEARCH( ) to the $p$*-graphs shown in Fig. 3, we will encounter
three repeated nodes of Case 1: $v_{3}$, $v_{2}$, and $v_{1}$.

  * •

Checking $v_{3}$. As shown in Example 1, by this checking, we will find a
subset of two conjunctions $\\{$$D_{2}$, $D_{5}$$\\}$ satisfied by a truth
assignment $\\{$$c_{1}$ = 0, $c_{2}$ = 1, $c_{3}$ = 1, $c_{4}$ = 0, $c_{5}$ =
1, $c_{6}$ = 1$\\}$. However, when creating $T$ at the very beginning, a
subset of conjunctions $\\{$$D_{1}$, $D_{2}$, $D_{5}$$\\}$ has already been
found (see node $v_{7}$ in Fig. 2), which can be satisfied by a same truth
assignment: $c_{1}$ = 1, $c_{2}$ = 1, $c_{3}$ = 1, $c_{4}$ = 1, $c_{5}$ = 1,
$c_{6}$ = 1. (See the path from the root to $v_{7}$ in Fig. 2.) Since
$\\{$$D_{1}$, $D_{2}$, $D_{5}$$\\}$ is larger than than $\\{$$D_{2}$,
$D_{5}$$\\}$, the result obtained by this checking should not be kept around.

  * •

Checking $v_{2}$. When we encounter this repeated node of Case 1 during the
generation of $G^{\prime}$, we will find two subgraphs in $G$[$v_{2}$],
respectively rooted at $v_{3}$ and $v_{11}$, as shown in Fig. 10.

Figure 10: Two subgraphs in $G$[$v_{2}$] and a upBound.

With respect to $v_{2}$, we will first calculate all the relevant reachable
subsets through spans for all the nodes on the tree path from root to $v_{2}$
in $G$. Altogether we can figure out five reachable subsets through spans
shown below. Among them, associated with $v_{1}$ (on the tree path from root
to $v_{2}$ in Fig. 3), we have

\- $\textit{RS}_{v_{1}}$[$c_{4}$] = $\\{$$v_{4}$, $v_{11}$$\\}$,

due to the following two spans (see Fig. 3):

\- $\\{$$v_{1}$ $\xrightarrow{3}$ $v_{4}$, $v_{1}$ $\xrightarrow{6}$
$v_{11}$$\\}$.

Associated with $v_{2}$ (the repeated node itself) have we the following four
reachable subsets through spans:

\- $\textit{RS}_{v_{2}}$[$c_{4}$] = $\\{$$v_{4}$, $v_{11}$$\\}$,
\- $\textit{RS}_{v_{2}}$[$c_{5}$] = $\\{$$v_{5}$, $v_{8}$, $v_{12}$$\\}$,
\- $\textit{RS}_{v_{2}}$[$c_{6}$] = $\\{$$v_{6}$, $v_{9}$$\\}$,
\- $\textit{RS}_{v_{2}}$[$\$$] = $\\{$$v_{10}$, $v_{13}$$\\}$,

due to four groups of spans shown below:

\- $\\{$$v_{2}$ $\xrightarrow{3,5}$ $v_{4}$, $v_{2}$ $\xrightarrow{6}$
$v_{11}$$\\}$,
\- $\\{$$v_{2}$ $\xrightarrow{5}$ $v_{5}$, $v_{2}$ $\xrightarrow{2}$ $v_{8}$,
$v_{2}$ $\xrightarrow{6}$ $v_{12}$$\\}$,
\- $\\{$$v_{2}$ $\xrightarrow{5}$ $v_{6}$, $v_{2}$ $\xrightarrow{2}$
$v_{9}$$\\}$,
\- $\\{$$v_{2}$ $\xrightarrow{2}$ $v_{10}$, $v_{2}$ $\xrightarrow{6}$
$v_{13}$$\\}$.

In terms of these reachable subsets through spans, we can establish the
corresponding upper boundary $\\{$$v_{4}$, $v_{8}$, $v_{11}$$\\}$ (which is
illustrated as a thick line in Fig. 10). Then, we can determine over what
subgraphs a trie-like graph will be established, on which the algorithm will
be recursively executed.

In Fig. 11(a), we show the trie-like graph built over the three $p$*-subgraphs
(starting respectively from $v_{4}$, $v_{8}$, $v_{11}$ on the upBound shown in
Fig. 10), in which $v_{4-11}$ stands for the merging of $v_{4}$ and $v_{11}$,
and $v_{5-12}$ for the merging of $v_{5}$ and $v_{12}$. Especially, $v_{2}$ is
involved as a braching node, working as a bridge between the newly contructed
trie-like graph and the rest part of $G$. (See operation $D^{\prime}$ =
$\\{$$v$$\\}$ $\cup$ $D^{\prime}$ in line 6 of Alrorithm 3.)

Figure 11: A trie-like graph and a path.

By a recursive call of SEARCH( ), we will create its layed graph as shown in
Fig. 12. At level 2 in Fig. 12, we can see a repeated nodes of Case 1: node
$v_{5-12}$. Then, we will make a recursive call of the algorithm, generating
an upBound $\\{$$v_{7}$, $v_{13}$$\\}$. Accordingly, we will find a single
path as shown in Fig. 11(b), by which we can figure out another largest subset
of conjunctions $\\{$$D_{3}$, $D_{6}$$\\}$, which can be satisfied by a
certain truth assignment. We notice that the subset associated with this path
is $\\{$$D_{3}$, $D_{6}$$\\}$, instead of $\\{$$D_{3}$, $D_{5}$, $D_{6}$$\\}$.
It is because the span from $v_{5-12}$ to $v_{7}$ (in Fig. 11(a)) is labeled
with 3 and $D_{5}$ should be removed.

Figure 12: A naive bottom-up search of $G$.

When we encounter the second repeated node $v_{2}$, we will create a set of
RS’s shown below:

  * -

$\textit{RS}_{v_{1}}$ = $\emptyset$, (Note that any RS with |RS| < 2 will not
be considered.)

  * -

$\textit{RS}_{v_{2}}$[$c_{5}$] = $\\{$$v_{5-12}$, $v_{8}$$\\}$, (due to the
span $v_{2}$ $\xrightarrow{5}$ $v_{5-12}$ and the tree edge $v_{2}$
$\rightarrow$ $v_{8}$.)

  * -

$\textit{RS}_{v_{2}}$[$c_{6}$] = $\\{$$v_{6}$, $v_{9}$$\\}$, (due to the spans
$v_{2}$ $\xrightarrow{5}$ $v_{6}$ and $v_{2}$ $\xrightarrow{2}$ $v_{9}$.)

In terms of these RSs, we construct the corresponding upBound $\\{$$v_{5-12}$,
$v_{8}$$\\}$, and create a trie-like graph as shown in Fig. 13(a). The only
branching node in this graph is $v_{5-12-8}$. Checking this node, we will
finally get a single path as shown in Fig. 13(b), indicating a new subset of
conjunctions which can be satisfied by a certain truth assignment.

Figure 13: Illustration for the recursive execution of the algorithm.

In the whole working process, a simple but very powerful heuristics can be
used to improve efficiency. Let $\alpha$ be the size of the largest subset of
conjunctions found up to now, which can be satisfied by a certain truth
assignment. Then, any recursive call of the algorithm over a smaller than
$\alpha$ subset of $p$*-subgraphs will be surpressed.

After $v_{2}$ is removed from the corresponding levels in $G^{\prime}$, the
next repeated node $v_{1}$ of Case 1 will be checked in a way similar to
$v_{3}$ and $v_{2}$.

Concerning the correctness of Algorithm 3, we have the following proposition.

######  Proposition 3.

Let $G$ be a trie-like graph established over a logic formula in DNF. Applying
Algorithm 3 to $G$, we will get a maximum subset of conjunctions satisfying a
certain truth assignment.

###### Proof.

To prove the proposition, we first show that any subset of conjunctions found
by the algorithm must be satisfied by a same truth assignment. This can be
observed by the definition of RSs and the corresponding upBounds.

Then, we need to show that any subset of conjunctions, which can be satisfied
by a certain truth assignment, can be found by the algorithm. For this
purpose, consider a subset of conjunctions $D^{\prime}$ which can be satisfied
by a truth assignment represented by a path

$v_{1}$ $\rightarrow$ $v_{2}$ … $v_{i-1}$ $\rightarrow$ $v_{i}$ $\rightarrow$
$v_{j}$ … $\rightarrow$ $v_{m}$,

in which $v_{i}$ $\rightarrow$ $v_{j}$ corresponds to a span. According to the
definition of RSs, the algorithm will find this path. This analysis can be
extended to general cases that a path contains one or more spans. ∎

##  V Time complexity analysis

The total running time of the algorithm consists of three parts.

The first part $\tau_{1}$ is the time for computing the frenquencies of
variable appearances in $D$. Since in this process each variable in a $D_{i}$
is accessed only once, $\tau_{1}$ = O($nm$).

The second part $\tau_{2}$ is the time for constructing a trie-like graph $G$
for $D$. This part of time can be further partitioned into three portions.

  * •

$\tau_{21}$: The time for sorting variable sequences for $D_{i}$’s. It is
obviously bounded by O($nm$log2 $m$).

  * •

$\tau_{22}$: The time for constructing $p$*-graphs for each $D_{i}$ ($i$ = 1,
…, $n$). Since for each variable sequence a transitive closure over its spans
should be first created and needs O($m^{2}$) time, this part of cost is
bounded by O($nm^{2}$).

  * •

$\tau_{23}$: The time for merging all $p$*-graphs to form a trie-like graph
$G$, which is also bounded by O($nm^{2}$).

The third part $\tau_{3}$ is the time for searching $G$ to find a maximum
subset of conjunctions satisfied by a certain truth assignment. It is a
recursive procedure. To analyze its running time, therefore, a recursive
equation should established. Let $l$ = $nm$ (the upper bound on the number of
nodes in $T$). Assume that the average outdegree of a node in $T$ is $d$. Then
the average time complexity of $\tau_{3}$ can be characterized by the
following recurrence based on an observation that for each branching node a
recursive call of the algorithm will be performed:

$\displaystyle\varGamma(l)=\left\\{\begin{array}[]{ll}O(1),&\text{if $l$
$\leq$ a constant,}\\\ \\\ \sum_{i=1}^{\lceil
log_{d}\;l\rceil}d^{i}\varGamma({\frac{l}{d^{i}}})+O(l^{2}m),&\text{otherwise.}\\\
\end{array}\right.$ (4)

Here, in the above recursive equation, O($l^{2}m$) is the cost for generating
all the reachable subsets of a node through spans and upper boundries,
together with the cost for generating all the trie-like subgraphs for each
recursive call of the algorithm. We notice that the size of all the RSs
together is bounded by the number of spans in $G$, which cannot ne larger than
O($lm$).

From (4), we can get the following inequality:

$\varGamma(l)\leq d\cdot log_{d}\;l\cdot\varGamma({\frac{l}{d}})+O(l^{2}m).$
(5)

Solving this inequality, we will get

$\begin{array}[]{ll}\varGamma(l)\leq d\cdot
log_{d}\;l\cdot\varGamma({\frac{l}{d}})+O(l^{2}m)\\\ \\\ \quad\quad\leq
d^{2}(log_{d}\;l)(\;log_{d}\frac{l}{d})\varGamma(\frac{l}{d^{2}})+\;(log_{d}\;l)\;l^{2}m+\;l^{2}m\\\
\\\ \quad\quad\leq...\;...\\\ \\\ \quad\quad\leq d^{\lceil
log_{d}^{l}\rceil}(log_{d}\;l)\;(log_{d}(\frac{l}{d}))\;...\;(\;log_{d}\frac{l}{d^{\lceil
log_{d}^{l}\rceil}})\\\ \\\
\quad+\;l^{2}m((log_{d}\;l)(log_{d}(\frac{l}{d}))\;...\;(log_{d}\frac{l}{d^{\lceil
log_{d}^{l}\rceil}})+...+log_{d}\;l+1)\\\ \\\ \quad\quad\leq
O(l(log_{d}\;l)^{log_{d}\;l}+\;O(l^{2}m(log_{d}\;l)^{log_{d}\;l})\\\ \\\
\quad\quad\sim O(l^{2}m\;(log_{d}\;l)^{log_{d}\;l}).\end{array}$ (6)

Thus, the value for $\tau_{3}$ is $\varGamma(l)$ $\sim$
O($l^{2}m\;(log_{d}\;l)^{log_{d}\;l}$).

From the above analysis, we have the following proposition.

######  Proposition 4.

The average running time of our algorithm is bounded by

$\begin{array}[]{ll}\Sigma^{3}_{i=1}\tau_{i}=O(nm)+(O(nm\;log_{2}\;m)+2\times
O(nm^{2}))\\\ \\\
\quad\quad\quad\quad+\;O(l^{2}m\;(log_{d}\;l)^{log_{d}\;l})\\\ \\\ \hskip
31.2982pt=O(n^{2}m^{3}(log_{d}\;nm)^{log_{d}\;nm}).\\\ \end{array}$ (7)

But we remark that if $d$ = 1, we can immediately determine the maximum subset
of satisfied conjunctions. It is just the set of conjunctions associated with
the leaf node of the unique $p$*-graph.

Thus, it is reasonable to assume that we have $d$ > 1 in (7).

The upper bound given above is much larger than the actual running time and
cannot properly exhibit the quality of the algorithm. In the following, we
give a worst-case time analysis which shows a much better running time
complexity.

First, we notice that in all the generated trie-like subgraphs, the number of
all the branching nodes is bounded by O($nm$). But each branching node may be
involved in at most O($n$) recursive calls (see the analysis given below) and
for each recursive call at most O($nm^{2}$) time can be required to create the
corresponding trie-like subgraph. Thus, the worst-case time complexity of the
algorithm is bounded by O($n^{3}m^{3}$).

We need to make clear that each branching node can be involved at most in
O($n$) recursive calls. For this, we have the following analysis. Let $v$ be a
top branching node, which does not have any ancestor branching node. Let $P$
be a longest path from root through $v$ to a leaf node in $G$. Then,
corresponding to each descendant $u$ of $v$ on $P$, we may have a recursive
call on a set of subgraphs each rooted at a node on the upBound with respect
to $v$ (see line 6 of Algorithm 3). Thus, in the worst case, $v$ can be
involved in $n$ \- 1 recursive calls. We call all such recursive calls a
$v$-recursion. Now, we consider another branching node $v^{\prime}$, which is
a descendant of $v$. But between $v$ and $v^{\prime}$ there is not any other
branching node. For the same reason, $v^{\prime}$ can be involved in $n$ \- 2
recursive calls. But it could also be involved in a $v$-recursion. So,
$v^{\prime}$ can be involved at most in $n$ \- 2 + 1 = $n$ \- 1 recursive
calls. Further, let $v^{\prime\prime}$ be a descedant branching node of
$v^{\prime}$. Then, $v^{\prime\prime}$ can also be involved in $n$ \- 1
recursive calls according to the above analysis. It is because besides $n$ \-
3 recursive calls involving $v^{\prime\prime}$, $v^{\prime\prime}$ can also be
involved in a $v$-recursion and a $v^{\prime}$-recursion.

In a similar way, we can analyze all the other branching nodes.

##  VI Conclusions

In this paper, we have presented a new method to solve the 2-MAXSAT problem.
The worst-case time complexity of the algorithm is bounded by O($n^{3}m^{3}$),
where $n$ and $m$ are respectively the numbers of clauses and variables of a
logic formula $C$ (over a set $V$ of variables) in CNF. The main idea behind
this is to construct a different formula $D$ (over a set $U$ of variables) in
DNF, according to $C$, with the property that for a given integer $n$* $\leq$
$n$ $C$ has at least $n$* clauses satisfied by a truth assignment for $V$ if
and only if $D$ has least $n$* conjunctions satisfied by a truth assignment
for $U$. To find a truth assignment that maximizes the number of satisfied
conjunctions in $D$, a graph structure, called $p$*-graph, is introduced to
represent each conjunction in $D$. In this way, all the conjunctions in $D$
can be represented as a trie-like graph. Searching $G$ bottom up, we can find
the answer efficiently.

## References

  * [1] J. Argelich, et. al., _MinSAT versus MaxSAT for Optimization Problems,_ International Conference on Principles and Practice of Constraint Programming, 2013, pp. 133-142.
  * [2] S. A. Cook, _The complexity of theorem-proving procedures,_ in: Proc. of the 3rd Annual ACM Symposium on the Theory of Computing, 1971, pp. 151-158.
  * [3] Y. Djenouri, Z. Habbas, D. Djenouri, _Data Mining-Based Decomposition for Solving the MAXSAT Problem: Toward a New Approach,_ IEEE Intelligent Systems, Vol. No. 4, 2017, pp. 48-58.
  * [4] C. Dumitrescu, _An algorithm for MAX2SAT,_ International Journal of Scientific and Research Publications, Volume 6, Issue 12, December 2016.
  * [5] Y. Even, A. Itai, and A. Shamir, _On the complexity of timetable and multicommodity flow problems,,_ SIAM J. Comput., 5 (1976), pp. 691-703.
  * [6] M. R. Garey, D. S. Johnson, and L. Stockmeyer, _Some simplified NP-complete graph problems,_ Theoret. Comput. Sci., (1976), pp. 237-267.
  * [7] R. Impagliazzo and R. Paturi, _On the complexity of k-sat. J. Comput._ , Syst. Sci., 62(2):367–375, 2001.
  * [8] M.S. Johnson, _Approximation Algorithm for Combinatorial Problems_ , J. Computer System Sci., 9(1974), pp. 256-278.
  * [9] E. Kemppainen, _Imcomplete Maxsat Solving by Linear Programming Relaxation and Rounding_ , Master thesis, University of Helsinki, 2020.
  * [10] M. Krentel, _The Complexity of Optimization Problems_ , J. Computer and System Sci., 36(1988), pp. 490-509.
  * [11] R. Kohli, R. Krishnamurti, and P. Mirchandani, _The Minimum Satisfiability Problem_ , SIAM J. Discrete Math., Vol. 7, No. 2, June 1994, pp. 275-283.
  * [12] D.E. Knuth, _The Art of Computer Programming_ , Vol.1, Addison-Wesley, Reading, 1969.
  * [13] D.E. Knuth, _The Art of Computer Programming_ , Vol.3, Addison-Wesley, Reading, 1975.
  * [14] A. Kügel, _Natural Max-SAT Encoding of Min-SAT_ , in: Proc. of the Learning and Intelligence Optimization Conf., LION 6, Paris, France, 2012.
  * [15] C.M. Li, Z. Zhu, F. Manya and L. Simon, _Exact MINSAT Solving_ , in: Proc. of 13th Intl. Conf. Theory and Application of Satisfiability Testing, Edinburgh, UK, 2010, PP. 363-368.
  * [16] C.M. Li, Z. Zhu, F. Manya and L. Simon, _Optimizing with minimum satisfiability_ , Artificial Intelligence, 190 (2012) 32-44.
  * [17] A. Richard, _A graph-theoretic definition of a sociometric clique_ , J. Mathematical Sociology, 3(1), 1974, pp. 113-126.
  * [18] C. Papadimitriou, _Computational Complexity_ , Addison-Wesley, 1994.
  * [19] Y. Shang, _Resilient consensus in multi-agent systems with state constraints_ , Automatica, Vol. 122, Dec., 2001, 109288.
  * [20] V. Vazirani, _Approximaton Algorithms_ , Springer Verlag, 2001.
  * [21] M. Xiao, _An Exact MaxSAT Algorithm: Further Observations and Further Improvements_ , Proc. of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22).
  * [22] H. Zhang, H. Shen, and F. Manyà, _Exact Algorithms for MAX-SAT_ , Electronic Notes in Theoretical Computer Science 86(1):190-203, May 2003.