/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Q7E Consider a special case of 3SAT ... [FREE SOLUTION] | 91影视

91影视

Log out

Learning Materials

Features

Discover

Chapter 8: Q7E (page 279)

Consider a special case of 3SAT in which all clauses have exactly three literals, and each variable appears exactly three times. Show that this problem can be solved in polynomial time. (Hint: create a bipartite graph with clauses on the left, variables on the right, and edges whenever a variable appears in a clause. Use Exercise 7.30 to show that this graph has a matching.)

Short Answer

Expert verified

The given statement has been proved.

Step by step solution

01

Consider the given information

Firstly, need to design a bipartite graph where all clauses lie on the left side and all the variables lies on the right side of the graph.

Suppose there are total clauses and variables and m鈮�n. Consider the variables w, x, y and z.

02

To prove (W ∨ Y ∨ Z) ∧(W ∨¬ Y ∨¬ Z) ∧(X ∨¬ Y ∨¬ Z) 

Proof:

Firstly, design a bipartite graph for all clauses that lie on the left side and all the variables that lies on the right side of the graph.

From Figure 1, the complete clause is provided below:

W鈭�Y鈭�Z鈭�W鈭�卢X鈭�卢Y鈭�X鈭�卢Y鈭�卢Z

03

 Step 3: To find subset of S 

To find out that for any subset of clauses, there cannot be less than variables connected to it.

Thus, find matching between clauses and variables according to Hall鈥檚 theorem.

This gives an assignment by which there is at least a literal which holds true in every clause.

Like, W鈫�True,Y鈫�True,Z鈫�False, X and can be either true or false.

Hence, the given statement has been proved.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91影视!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Search versus decision. Suppose you have a procedure which runs in polynomial time and tells you whether or not a graph has a Rudrata path. Show that you can use it to develop a polynomial-time algorithm for RUDRATA PATH (which returns the actual path, if it exists).

On page 266we saw that 3SATremainsNP-complete even when restricted to formulas in which each literal appears at most twice.

(a)Show that if each literal appears at mostonce,then the problem is solvable in polynomial time.

(b)Show that INDEPENDENT SET remains NP-complete even in the special case when all the nodes in the graph have degree at most 4.

Show that if P=NP then the RSA cryptosystem (Section 1.4.2) can be broken in polynomial time.

Question: In an undirected graph G=(V,E), we say D鈯�Vis a dominating set if every v鈭�V is either in D or adjacent to at least one member of D. In the DOMINATING SET problem, the input is a graph and a budget , and the aim is to find a dominating set in the graph of size at most , if one exists. Prove that this problem is NP-complete.

Proving NP-completeness by generalization. For each of the problems below, prove that it is NP-complete by showing that it is a generalization of some NP-complete problem we have seen in this chapter.

  1. SUBGRAPH ISOMORPHISM: Given as input two undirected graphsG and H, determine whetherG is a subgraph of H (that is, whether by deleting certain vertices and edges ofH we obtain a graph that is, up to renaming of vertices, identical toG ), and if so, return the corresponding mapping ofV(G) intoV(H) .
  2. LONGEST PATH: Given a graph role="math" localid="1658141805147" Gand an integerg find inG a simple path of lengthg .
  3. MAX SAT: Given a CNF formula and an integer g, find a truth assignment that satisfies at least gclauses.
  4. DENSE SUBGRAPH: Given a graph and two integersa and b, find a set of a vertices ofG such that there are at leastb edges between them.
  5. SPARSE SUBGRAPH: Given a graph and two integersa andb , find a set of a vertices ofG such that there are at most bedges between them.
  6. SET COVER. (This problem generalizes two knownNP-complete problems.)
  7. RELIABLE NETWORK: We are given twon脳n matrices, a distance matrixdij and a connectivity requirement matrixrij , as well as a budgetb ; we must find a graph G=({1,2,.....,n},E)such that (1) the total cost of all edges isb or less and (2) between any two distinct verticesi andj there arerij vertex-disjoint paths.
See all solutions

Recommended explanations on Computer Science Textbooks

Computer Programming

Read Explanation

Game Design in Computer Science

Read Explanation

Problem Solving Techniques

Read Explanation

Databases

Read Explanation

Theory of Computation

Read Explanation

Blockchain Technology

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.