Question

Consider a special version of the 3SAT problem, where every clause has exactly 3 literals, and each variable appears at most 3 times. Show that this version of 3SAT can be solved in polynomial time, by giving a polynomial time algorithm that finds a satisfying assignment. HINT: Consider the bipartite graph with clauses on the left, and variables on the right. Connect a clause to a variable if the variable appears in the clause. Argue that this graph has a perfect matching. Then give an algorithm to find the perfect matching and find a satisfying assignment.

Answer 1

answer:

8.7 Consider a bipartite graph with clauses on the left and variables on the right. Consider any subset S of clauses

(left vertices).

This has exactly 3|S edges going out of It, since each clause has exactly 3 literals. Since each variable on the right has at most 3 edges coming into it, S must be connected to at least ISI variables on the right. Hence, this graph has a matching using Hall's theorem proved in problem 7.30.

This means we can match every clause with a unique variable which appears in that clause. For every clause, we set the matched variable appropriately to make the clause true, and set the other variables arbitrarily. This gives a satisfying. assignment. Since a matching can be found in polynomial time (using flow), we can construct the assignment in polynomial time.

note:

if you like the answer please give me up vote :)

thank you