=Paper=
{{Paper
|id=None
|storemode=property
|title=A minimum spanning tree for the #2SAT problem
|pdfUrl=https://ceur-ws.org/Vol-677/11_LANMR10_poster.pdf
|volume=Vol-677
}}
==A minimum spanning tree for the #2SAT problem==
https://ceur-ws.org/Vol-677/11_LANMR10_poster.pdf
A Minimum Spanning Tree
for the #2SAT Problem
Guillermo De Ita, Meliza Contreras, Pedro Bello
Faculty of Computer Science, Universidad Autónoma de Puebla
{deita,mcontreras,pbello}@cs.buap.mx
Abstract. #2SAT is a classical #P-complete problem. We present here,
a novel algorithm for given a 2-CF Σ, to build a minimum spanning tree
for its constraint graph GΣ assuming dynamic weights on the edges of
the input graph.
Keywords: Counting the Number of Models, Minimum Spanning Tree.
1. Introduction
Counting combinatorial objects over graphs has been an interesting and impor-
tant area of research in Mathematics, Physics, and Computer Sciences. Counting
problems, being mathematically interesting by themselves, are closely related to
important practical problems. For instance, reliability issues are often equivalent
to counting problems [2, 3, 5].
The techniques for building minimum spanning trees have been developed
assuming static weights on the edges of the graph. But for the #2SAT problem [4,
6], instead of static weights we consider dynamic weights determined by the signs
of the edges, as well as the number of partial models associated with the nodes.
We address the construction of the minimum spanning tree of a constraint graph
considering such dynamic weights.
2. Preliminaries
Let Σ be a 2-CF, the constraint graph of Σ is the undirected graph GΣ =
(V (Σ), E(Σ)), with V (Σ) = υ(Σ) and E(Σ) = {{υ(x), υ(y)} : {x, y} ∈ Σ},
i.e. the vertices of GΣ are the variables of Σ, and for each clause {x, y} in Σ
there is an edge {υ(x), υ(y)} ∈ E(Σ). Each edge has associated an ordered pair
(s1 , s2 ) of signs assigned as labels. For example, the signs s1 and s2 for the clause
{x ∨ y} are related to the signs of the literals x and y respectively, then s1 = −
and s2 = + and the edge is denoted as: x − + y which is equivalent to y + − x.
A connected component of G is a maximal induced subgraph of G. We say
that the set of connected components of Σ are the subformulas corresponding to
the connected components of GΣ . From now on, when we mention a 2-CF Σ,
we assume that Σ is a connected component graph.
107
3. Linear procedures for #2SAT
We present here, some procedures for computing the number of models of a for-
mula for basic topologies of a graph.
Procedure A: If Σ is a path:
The first pair (α0 , β0 ) is (1,1) since for any logical value to y0 , f0 is satisfied.
(αi , βi ) associated with each variable yi , i = 1, .., m is computed according to
the signs: ²i , δi of the literals in the clause ci , by the recurrence (1). As Σ = fm
then #SAT (Σ) = µm = αm + βm . We denote with 0 →0 the application of one
of the four rules in the recurrence.
(βi−1 ,µi−1 ) if (²i , δi ) = (0, 0)
(µi−1 ,βi−1 ) if (²i , δi ) = (0, 1)
(αi , βi ) = (1)
(αi−1 ,µi−1 ) if (²i , δi ) = (1, 0)
(µi−1 ,αi−1 ) if (²i , δi ) = (1, 1)
a) - b)
+ + + - + + + + + - - + + - +
x1 x2 x3 x4 x5 x1 x2 x3 x4 x5
(1,1) (2,1) (2,3) (5,3) (8,5) =13 models (1,1) (2,1) (1,3) (4,1) (5,1) =6 models
Fig. 1. a) Counting models on a monotone paths b)Counting models on a
changing sign path
Example 1 Let Σ = {{x1 , x2 }, {x2 , x3 }, {x3 , x4 }, {x4 , x5 }} be a path, the series
(αi , βi ), i ∈ [[5]] is computed according to the signs of the edges, as it is illustrated
in figure (1a). A similar path but with complementary signs on the nodes is
shown in (1b).
Let us consider the class P of Boolean functions where their constraint graphs
are paths. For example, figures (1a) and (1b) represent Boolean path functions.
We denote as Pn+ a monotone path with n nodes and where each variable ap-
pears with the same sign (like in (1a)), while Pn−+ is the n path where the
occurrences of the variables are with complementary signs (like in (1b)), we
call to this last Boolean formula a changing sign path. Let #+ : IN → IN
be the function which for a n ∈ IN , it considers a monotone path Pn+ ∈ P
holding that #+ (n) = #SAT (Pn+ ). We can estimate the rate of growth of
#+ since it corresponds with the growth of #SAT (Pn+ )³when ´the number of
√
variables n growth. As #SAT (Pn+ ) ∈ O(φn ) with φ = 1+2 5 ≈ 1.618 [1],
³³ √ ´n ´
1+ 5
then, #+ (n) ∈ O 2 . Let #−+ : IN → IN be a function which for
a n ∈ IN it considers a changing sign path Pn−+ ∈ P, and #−+ holds that
108
#−+ (n) = #SAT (Pn−+ ). Thus, the rate of growth of the function #−+ is the
same that the growth of #SAT (Pn−+ ) when the number of variables n growth,
and as #SAT (Pn−+ ) ∈ O(n) [1], then #−+ ∈ O(n). Comparing the rates of
growth for P + and P −+ , we obtain O(#SAT (Pn+ )) > O(#SAT (Pn−+ )).
Procedure B: If Σ is a tree:
Let Σ be a 2-CF where its associated constraint graph GΣ is a tree. We de-
note with (αv , βv ) the pair associated with the node v (v ∈ GΣ ). We compute
#SAT (Σ) considering the methodology used in [1].
Example 2 Let B7+ a monotone balanced tree, like in (2a). And B7+− the binary
balanced tree where each internal node has complementary signs on its incident
child-edges. Applying Count M odels f or trees to both trees, it starts assign-
ing the pair (1,1) to the leaf nodes. The number of models at each level of the
tree is shown in Figure 2. At the level of the root node, the procedure obtains
#SAT(Bn+ ) = 25 + 16 = 41. And for the second tree, #SAT(B7+− ) = 8 + 8 = 16.
(25,16) = 41 (8,8) = 16
a) b)
+ + (5,4) (2,4)
- + (4,2)
(5,4)
(4,1) + - (1,4) (2,2) + + (2,2)
(1,2) (2,1) (2,1) (1,2)
(2,1) (1,2) (1,2)
(2,1)
- - + -
+ + - +
+ + - + - + - -
(1,1) (1,1) (1,1) (1,1) (1,1) (1,1) (1,1)
(1,1)
Fig. 2. a) Counting models over a monotone balanced tree, b) Counting
models over a non-monotone balanced tree
For monotone Boolean formulas whose constraint graph is a balanced binary
tree, like in example 2, we can express how the number of models changes ac-
cording with the number of nodes of the tree. E.g. for a monotone binary tree
with 3 nodes (α3 , β3 ) = (22 , 12 ) = (4, 1). The following balanced binary tree
has 7 nodes and (α7 , β7 ) = (52 , 42 ) = (25, 16). The following tree has 15 nodes
and (α15 , β15 ) = (412 , 252 ) = (1681, 625). In general, we obtain the following
recurrence relation for the balanced monotone binary trees Bn+ with n nodes:
#SAT(Bn+ ) = Fn/2 2 4
+ Fn/4 being Fi the i-th Fibonacci number. This recurrence
relation has an order of growth of O(2(3/4)n ).
On the other hand, the upper bound for the class of binary formulas where
there are complementary signs on the child-edges on each internal node, tree
n
denoted as Bn+− is given by #SAT (Bn+− ) ∈ O(2 2 ). The previous upper bounds
establish a hierarchy for #SAT according to the topology of the constraint
graphs, given as: O(#SAT (Pn−+ )) ≤ O(#SAT (Bn+− )) ≤ O(#SAT (Pn+ )) ≤
O(#SAT (Bn+ )).
109
4. Building the Minimum Spanning Tree
Let A1 , . . . , An be the sequence of initial charges obtained by the procedures (A)
or (B) for computing #SAT(Σ). Now, we build a new sequence of pairs which
represent the final charges (or just the charges) Bn , . . . , B1 , being Bi the charge
of the variable xi ∈ υ(Σ), computed as:
Bn = An
(2)
Bn−i = balance(An−i , Bn−i+1 ), i = 1, ..., n − 1
balance(A, B) is a binary operator between two pairs, e.g. if x s1ys2 is an edge
of the constraint graph GΣ , and assuming A = (αx , βx ) be the initial charge of
the variable x, B = (ay , by ) be the final charge of the variable y, then balance
produces a new pair (ax , bx ) which will be the final charge for x, i.e. #SAT(Σ) =
βx
ax + bx . Let µx = αx + βx and µy = ay + by . Let P1 = α µx and P0 = µx be the
x
proportion of the number of 1’s and 0’s in the initial charge of the variable x.
The final charge (ax , bx ) is computed, as:
ax = ay · P1 + by ; bx = µy − ax if(s1 , s2 ) = (+, +)
bx = by · P0 + ay ; ax = µy − bx if(s1 , s2 ) = (−, −)
(3)
bx = by · P0 + ay ; ax = µy − bx if(s1 , s2 ) = (+, −)
ax = ay · P1 + by ; bx = µy − ax if(s1 , s2 ) = (−, +)
In the case that the coefficients P0 or P1 are not integer numbers, the follow-
ing formulas are applied for computing the charge of x.
ax = (by − ay ); bx = (µy − ax ) if(s1 , s2 ) = (−, −)
ax = (ay − by ); bx = (µy − ax ) if(s1 , s2 ) = (−, +)
(4)
bx = (by − ay ); ax = (µy − bx ) if(s1 , s2 ) = (+, −)
bx = (ay − by ); ax = (µy − bx ) if(s1 , s2 ) = (+, +)
Note that the essence of the rules in balance consists in applying the inverse
operation utilized via recurrence (1) during the computation of #SAT(Σ). Fur-
thermore, in the case of bifurcations from a father node to a list of child nodes,
the application of recurrence (3) or (4) remains valid since each branch edge has
its respective pair of signs.
4.1. A Procedure for Building Spanning Trees for #2SAT
Given a 2-CF Σ and its constraint graph GΣ , a minimum spanning tree, denoted
by TΣ , is a tree containing all vertices of GΣ and such that #SAT (AΣ ) ≥
#SAT (Σ) and #SAT (AΣ ) is minimum into the set of all spanning trees of GΣ .
When GΣ contains cycles, our proposal works like the well known Kruskal’s
algorithm. An initial spanning tree AΣ = (V (GΣ ), P Edges) is formed by all
vertices of GΣ because all vertices are connected components by themselves, and
all pendant edge of G are edges of the spanning tree (if there are not pendant
edges then an empty set is initially assigned to P Edges).
110
a) b)
X1 + - X1
-
+
+ +
X2 X2
- -
+ +
- + - - -
X3 X4 X3 X4
- - +
+ +
-
X5 X6 X5 X6
+ - +
c) d)
X1 (1,4)
- X1
(2,4)
+ (2,5)
+
X2 (1,1) X2
(5,1) (1,1)
(2,1) - (2,1)
(6,1)
(2,2) (2,2)
+ (3,2)
- (4,2)
-
X3 X4 X3 X4 (4,3)
- (6,1) (2,1)
+ + (3,1)
X5 X6
(3,1) (4,1)
X5 X6
+ (3,2) - (5,1)
+
(2,1) (3,3) (6,1)
(3,1)
(3,1) (3,4)
Fig. 3. Phases on the construction of the minimum spanning tree from an
initial constraint graph
.
The first step of our procedure consists in detecting the potential edges which
could generate change of signs when a node will be visited,(see fig. 3b). In each
step, each edge with one of its end-points in a node of AΣ and the other end-
point in a node not included in AΣ . While the procedure detects an edge e ∈ E
which generate change of signs on the incident edges of a same node, such edge
e is added to AΣ . When there are more than one edge E generating change of
signs or there are not such edges the procedure reviews how increase the number
of models when an edge e ∈ E would be added to AΣ , for this in each node an
inverse counting is calculated ,(see fig. 3c). The resulting spanning tree (see fig.
3d) with a total number of models of 7=6+1.
The edge e ∈ E which infers a minimal increment on #SAT(AΣ ) with respect
to any other edge in E, is selected to be added to AΣ . Notice that the increment
on the number of models depends mainly of the signs of e as well as the charge
of the two-endpoints of e. There are a set of strategies used for detecting the
edges in (E(GΣ ) − E(AΣ )) which infer minimal increment on #SAT(AΣ ). Such
strategies are: In general if two edges e1 and e2 generate the same increment on
the number of models of AΣ e1 is preferred over e2 if e1 could bring about a
change of signs, in the following steps, on its incident node, if the edge e connects
AΣ with one extra-node and generates complementary signs on one of its end-
points, then e is an optimal selection, and it is preferable to obtain a path than
a tree when the signs on the edges are the same.
111
Algorithm 1 Procedure Spanning T ree(GΣ ) (Input: GΣ = (V (G), E(G)))
Let P Edges = {e ∈ E(GΣ ) : e is a pendant edge };
All Edges := E(G) − P Edges; Cs := ∅; {Set of potential edges}
AΣ := (V (G), P Edges); {all pendant edges are part of the Tree}
CandEdge = SelectC andidateEdges(All Edges) {Set of candidate semi-edges }
F irstEdge = U nionC andidateEdges(CandEdge) {looking for a complete edge}
if F irstEdge <> ∅ then
E(AΣ ) := E(AΣ ) ∪ {F irstEdge}; Initialize(V ect M odels, 1, 1) ;
Count M odels(AΣ , V ect M odels); InverseOrderCount(AΣ , V ect M odels);
end if
while (All Edges <> ∅) do
Count M odels(All Edges, V ect M odels); {count models by each potential edge}
Sel Edge = min{V ect M odels}; {select the edge which minimum incremental}
if |Sel Edge| > 1 then
Cs = F ind(T est, AΣ ); {looking for edges which could generate change of signs}
T est = complete(Cs); {choose edges generating change of sign on the nodes}
Sel Edge = F irst(T est); {Select an edge keeping potential change of sign}
end if
All Edges := All Edges − {Sel Edge}; E(AΣ ) := E(AΣ ) ∪ {Sel Edge};
All Edges := All Edges − Edges Cycles(AΣ , All Edges); {delete cycles}
end while
5. Conclusions
We consider a new line of researching of building spanning trees with dynamic
weights determined by the signs of the edges and the partial number of models
associated with the endpoints of the edges. This consideration allows us, given
a 2-CF Σ, to build its minimum spanning tree AΣ such that #SAT(AΣ ) is a
minimum upper bound for #SAT(Σ). To build efficiently the minimum spanning
tree of a 2-CF is very helpful in the research for determining frontiers between
efficient and exponential counting procedures for the #2SAT problem.
References
1. De Ita G, Bello P, Contreras M, New Polynomial Classes for #2SAT Established
Via Graph-Topological Structure, Jour. Engineering Letters, Vol. 15 (2), (2007),
pp.250-258.
2. Dyer M., Greenhill C., Some #P-completeness Proofs for Colourings and Indepen-
dent Sets, Research Report Series, University of Leeds, 1997.
3. Greenhill Catherine, The complexity of counting colourings and independent sets
in sparse graphs and hypergraphs”, Computational Complexity, 9(1): 52-72, 2000.
4. Russ B., Randomized Algorithms: Approximation, Generation, and Counting, Dis-
tinguished dissertations Springer, 2001.
5. Roth D., On the hardness of approximate reasoning, Artificial Intelligence 82,
(1996), pp. 273-302.
6. Wahlström M., A Tighter Bound for Counting Max-Weight Solutions to 2SAT In-
stances, LNCS 5018, Springer-Verlag (2008), pp. 202-213.
112