Question

Algorithms

Given the following 3SAT formula, convert the problem to Independent Set and determine from there if the formula is satisfiable: $ = (x1 V x2 V x3) ^ (X1 V X2 V x3) ^ (X1 V x2 V x3)

Answer 1

I hope it help

thanks..

ANSWER:

Independent Set (IS):
Given an undirected graph G = (V, E) and an integer k does G
contain a subset V
0 of k vertices such that no two vertices in V
0 are adjacent to one
another.hence
Observe that by selecting the corresponding vertices from the clusters, we obtain
an independent set of size k = 4.

(x1 V 12 V X3) (T1 V 22 V 23) 2 conflict links Clause cluster 2 -- Fig. 3: Clause clusters for the clauses (21 V 12 V x3) and (T1 V x2 V 25). A formal description of the reduction is given below. The input is a boolean formula F in 3-CNF, and the output is a graph G and integer k. _3SAT to IS reduction k number of clauses in F for each (clause (21 V 22 V 23) in F) create a clause cluster consisting of three vertices labeled 21, 22, and x3 create edges (21,22), (22,63), (13,11) between all pairs of vertices in the cluster for each (vertex ci) create edges between I, and all its complement vertices Ti (conflict links) return (G, k) Given any reasonable encoding of F, it is an easy programming exercise to create G in polynomial time. As an example, suppose that we are given the 3-CNF formula: F = (21 V 22 V T3) ^ (TV x2 V 23) 1 (T1 V 22 V T3) ^ (21 V 12 V 23). The reduction produces the graph shown in Fig. 4. The clauses clusters appear in clockwise order starting from the top. The reduction k=4 correctness 2] = x2 = 1, x3 = 0 (b) Fig. 4: 3SAT to IS reduction. In our example, the formula is satisfied by the assignment Xi = 1, X2 = 1, and x3 = 0. Note that the literal xi satisfies the first and last clauses, 22 satisfies the second, and Tz satifies