Given a graph G and an integer k, describe how to compute a 2CNF formula and a v

Question

Given a graph G and an integer k, describe how to compute a 2CNF formula and a value L such that at least L clauses of can be satisfied if and only if there is an independent set in G of size k (or larger). To make things easy, you are allowed to duplicate the same clause in your formula as many times as you want. Naturally, the algorithm for computing this formula from G, k should work in polynomial time (and of course, you need to describe this algorithm). What is the value of L as a function of n, m and k where n = |V| and m = |E|?

Explanation / Answer

Let f= (x1,x2,x3....xn) be boolean variables. A literal is either a variable or its negation,xi. A clause is logical OR
of one or more distinct literals. The size of a clause is the number of literals in it. A 2CNF formula is a collection of m clauses
=( C1,C2,C3....Cm)

where each C i is of size at most two. 2CNF formula with n variables and m clauses, and k is a positive integer such that k m ,decide whether there exists an assignment to the n boolean variables that satis es at least k clauses.

A vertex cover is a subset V -> V such that for every edge in E , at least one of its endpoints is included in V0 .To every vertex in the graph, assign a boolean variable which is intended to be TRUE.if and only if the vertex is included in the vertex cover. Add clauses of size two corresponding to the edges, and clauses of size one
corresponding to the vertices. The clauses corresponding to edges may need to be repeated a number of times.

In the sequence of for 2CNF formulas,the only variables ipped are those whose values are different in s and t. To the best of our knowledge,our results on computing the shortest path in a recon guration graph for satisbility provide the rst exception to this pattern.In particular, we provide a class of Boolean formulas where the shortest reconguration path can ip variables that have the same values in s and t and yet the path can be computed in polynomial time. Insights from our results may lead to a better understanding of the role of the symmetric difference in computing shortest reconguration paths.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.