.Open 16 . Schedule .Table Date .Item Meet'g .Item $Study(2 pts) .Item Bring(5 pts) .Item $Topic(5 pts) .Item Notes .Row Mon May 22 .Item 15 .Item Chapter 10 sections 10.2, 10.3 .Item $Ex .Item NP-Complete .Row Wed May 24 .Item 16 .Item Chapter 10 sections 10.4, 10.5 .Item $Ex .Item Graph Problems & TSP .Row Mon May 29 .Item - .Item - .Item - .Item HOLIDAY .Row Wed May 31 .Item 17 .Item Chapter 11 sections 11.1, 11.2, 11.3 .Item $Ex .Item Co-NP & PSPACE .Close.Table . Note I won't be testing you on some of the more complicated reductions described in this chapter. An example is the construction described in Theorem 10.21 (Figures 10.9 and 10.10). .Open 10.4 Additional NP-Complete Problems 447 When you spot an NP-complete problem you change strategies from looking for an elegant algorithm to .Set Heuristics -- greedy, genetic, dynamic programming Special cases Approximations .Close.Set . 10.4.1 Describing NP-complete Problems 447 Problem::=following, .Net Name::string. Short_name::string. Given:: data defining an instance Goal:: properties defining a solution .Close.Net NP_Problem::=following, .Net $Problem. Proved_NP by: explanation that typically includes the short_name of another NP problem. .Close.Net . Ch 10.4 pp 447 -- Describing NP-complete Problems The book introduces new style form of definition. (problem, input, output, reduction from). Can there be more than one reduction to solve or show the problem is NP-complete. Yes.... there are many possible reductions. Some of these have been done, and some of these have been published.... and the book picks one of the published ones. . Graphs There is a pretty Graph on page 464. . 10.4.2 The Problem of Independent Sets 448 Don't be mislead -- this is not just an abstract problem. See Box on page 452. . Exercise 0 points -- draw a graph with 6 nodes. Scheduling MS presentations so that committee members can be present at each relevant presentation and also teach their classes. For Graph (N,E), I:subset(N), I is independent ::= for all i,j:N(if i!=j then {i,j} is not in E ). IS::=`Find independent sets in a undirected graph`. .Tuple Name: Independent sets Short_name: IS. Given: An undirected graph G=(N,E) with n nodes and e edges , k:1..n. Goal: YES if some I:subset(N)( |I|=k and I is an independent_set(G) ). proved NP by: Reducing 3SAT to IS. .Close.Tuple . Exercise 0 points -- find the maximal IS for your graph Why is this hard.... surely we start with the obviously independent set {} and add one node at a time until.... ? Answer: You can go up a blind alley that leads to a non-optimal solution. . Box Page 450 -- upper-bounding = optimizing . Ch 10.4.2 pp 450 -- Are Yes/No Problems Easier? Do we learn from a yes/no problem easier? Shouldn't we know why it is NP-complete with examples of problem or why it fail to be a NP-complete problem We use Yes/No problems because we've found proofs that use them -- apparently proofs for optimization problems are worse. . Theorem 10.18 IS is NP-complete Note the clever construction of a graph that encodes 3SAT as $IS. Structure of Proof .Box Prove IS is NP by constructing polynomial time NTM to solve IS. Prove IS is NP-hard... .List Construct a `G` and a `k` that should simulate 3SAT `E`. . Ch 10.4.2 pp 448-451 -- Independent Sets How is the 3-CNF expression derived from the figure below it... or vice versa, I'm not quite sure how to read it. Figure 10.8? . Ch 10.4 pp 449 -- Figure 10.8 How was the independent set constructed from this graph? .List Map the 3-CNF into a graph Each node models a literal in the formula. The nodes in the IS reflect true literals. Note. The nodes outside the IS model literals that can be true or false. Each clause is modeled as a cycle of 3 nodes. Complements are modeled by adding arcs. Setting the threshold `k` = `m` is vital. Because this makes sure that one literal in each clause is selected. The triangle of arcs for clause means that a literal is not chosen twice. .Close.List Prove: If `E` is satisfiable then there is an IS in G of size K. Prove: If there is an IS in G of size K then `E` is satisfiable. .Close.List .Close.Box . Example 10.19 and Figure 10.8 . Box on page 452 -- What is IS good for? The problem of scheduling a set of final exams so that no student has to be in more than one final at a time is an instance of $IS. . 10.4.3 The Node-Cover Problem 452 . Ch 10.4.3 pp 452 -- Additional NP-Complete Problems Could you go over the Node_cover Problem? NC::=`the node cover problem`, ... .Tuple Name: the node cover problem. Short_name: NC. Given: A graph G=(N,E) and upper limit k:0..|N|. Goal: Yes iff G has node cover with k or fewer nodes. .Close.Tuple For graph G=(N,E), , C: subset(N), C is a node_cover(G) iff for all {e1,e2}:E( either e1 or e2 is in C). . Exercise 0 points -- What is the minimum Node cover for your 6 node graph Note the `duality` between $NC and $IS. . Theorem 10.20 -- NC is NP_complete .Box NC is NP .List Guess a set of k nodes. Check to see if every edge in G has at least one end in the set. .Close.List Reduce IS to NC .List .Let G+k be an instance of IS with n nodes Construct instance of NC with k= n-k. .Close.Let Proof .List If... Only if... .Close.List .Close.List .Close.Box . 10.4.4 The Directed Hamilton-Circuit Problem 453 A directed graph is an (undirected) graph with arrows on the edges. The book gets to Hamiltonian cycles on undirected graphs by starting with directed ones. Undirected_Graph G::=(N,E) when N is a set and E is a set of sets {i,j} where i!=j and i,j are in N. (cycle): series of nodes, that begins and ends with the same node: (n1, n2, n3, ....., n[k], n[k+1] = n1) where for all i:1..k, {n[i], n[i+1]} is an edge). Directed_Graph D::=(N, E) when N is a set and E is a set of pairs (i,j) where i and j are in N. A directed graph can have arrows that loop back to the node the started at: (i,j). (directed_cycle): series of nodes, that begins and ends with the same node: (n1, n2, n3, ....., n[k], n[k+1] = n1) where for all i:1..k, (n[i], n[i+1]) is an edge). You need to know the idea of this construction but (in the final) I do not expect you duplicate the construction of the `gadgets`. .Tuple Hamilton-Circuit Problem HC Undirected graph G=(N,E). Output Yes if and only if G has a cycle that passes through each N once. Reduce the Directed Hamilton Circuit problem (DHC) to HC. See .See $HC below. .Close.Tuple . Exercise 0 points -- Does your 6 node graph have a Hamiltonian circuit? Special case of TSP: all edges have same length = 1. .Tuple Directed Hamilton-Circuit Problem DHC Directed graph G=(N,E). Output Yes if and only if G has a directed_cycle that passes through each N once. Reduce 3SAT to the Directed Hamilton Circuit problem (DHC) below. .Close.Tuple . Ch 10.4 pp 454 -- DHC & HC Why are these separated? If you know that a regular HC is NP-complete wouldn't that lead us to know the DHC is np-complete. Is there any major difference besides which way to go in these problems? Directed graphs are like a town where every street is a one way street and so the problem of finding a circuit through it is easier (fewer choices) and less likely (fewer options). It is possible that the DHC was proved first and then some one transformed it into the undirected HC. Until this connection is proved we can not claim that the two problems are `equivalent`. Indeed it may be that one is in some sense or other one is harder than the other: for example DHC may need O(n^10) nondeterministic steps and the other O(n^20). Both could still be in NP-complete but perform differently. You can probably go to HC first and derive DHC from it.... but I don't have the time to attempt it right now. . Exercise 0 points -- Draw a 6 node directed graph. . Exercise 0 points -- Does your 6 node directed graph have a Hamiltonian circuit. . Theorem 10.21 DHC is NP-complete Proof structure .List DHC is NP -- easy! Reduce 3SAT to DHC .Box many details and gadgets .Close.Box Proof of simulation .List if only-if .Close.List .Close.List . Example 10.22 and Figure 10.10 of DHC that models 3SAT . Figure 10.10 -- I don't quite understand . Ch 10.4 pp 454 -- DHC Could you please go over the proof for Theorem 10.21. The part where they connect all the sub graphs together at the end is confusing. . Ch 10.4.4 pp 453-459 -- The Directed Hamilton-Circuit Problem I'm terribly confused as to how the translation from an expression to a 'gadget' works. Could you explain the reasoning? . 10.4.5 Undirected Hamilton Circuits and the TSP 460 HC::problem=following, .Tuple Hamilton-Circuit Problem HC Undirected graph G=(N,E). Output Yes if and only if G has a cycle that passes through each N once. Reduce the Directed Hamilton Circuit problem (DHC) to HC. See below. .Close.Tuple . Theorem 10.23 HC is NP-complete Structure of Proof .List HC is NP -- OMITTED Reduce DHC to HC .List Model directed graph G[d] by a constructed undirected Graph G[u] with 3 times as many nodes that force a path to go in only one direction! Proof .Set if only-if .Close.Set .Close.List .Close.List TSP::=following .Tuple Traveling Salesperson Problem TSP An undirected graph G with integer weights on the edges and a limit k. Yes iff there is a HC of G with sum of weights <= k. Reduce from $HC .Close.Tuple . Theorem 10.24 TSP is NP-Complete Proof: the book omits a lot.... but it follows the normal pattern. Key thought: Given G construct G' such that solving TSP on G' solves HC on G. . 10.4.6 Summary of NP-Complete Problems 461 . Exercise -- 0 points -- write down the pattern of all the proofs of NP-completeness in this chapter Notice that all the proofs depend on creating a gimmick that transform a known problem into the unknown one. . Figure 10.12 The Family of NP-Complete problems in chapter 10 . Exercise -- reproduce this from memory . Exercise -- label each arc in Figure 10.12 with the theorem number that proves the result. . 10.4.7 Exercises for Section 10.4 462 . * Exercise 10.4.1 Cliques Work out a plan for this proof (with out any details/gadgets/gimmicks!) and then look at the book's web site to see what the gimmick is. . Can you explain why a Clique in NP complete? It seems like an easy thing to do. . *! Exercise 10.4.2 Coloring . Ch 10.4 pp 466 -- Why is the question of 2-colorability NP-complete? It seems as though once you've chosen on the color of one node, it automatically chooses the colors for all the other nodes in the graph. . !? Exercise 10.4.3 Fig 10.4 has only 20 nodes.... I found these problems easier than the "!" might indicate. The symmetry of the graph helps. I will except them as a "!" for grading however. . Ch 10.4 pp 464 -- Symmetry You noted in class that the symmetry makes problem 10.4.3 a lot easier. Is the problem of determining whether or not a graph has symmetry in P? My guess is NP-Complete. more $TBA. .Open Exercise 10.4.4 Nine more NP-complete Problems . Exercise 10.4.4a Subgraph isomorphism Easy to crate a CLIQUE solver from a subgraph isomorphism solver. . ! Exercise 10.4.4b Feedback edge set -- ERRORS The web site includes a couple of typographical errors. GJ75 state that the problem as stated is "Trivially in P"! Here is the corrected problem: Given a DIRECTED graph G with nodes N and arcs A, and an integer k, does G have a set of k arcs such that every directed cycle of G contains least one of the k arcs. Prove NP-complete by transforming $NC into this kind of problem. . ! Exercise 10.4.4c Linear integer programming . ! Exercise 10.4.4d Dominating Set problem . Exercise 10.4.4e firehouse problem . !! Exercise 10.4.4i The famous Knapsack Problem Subtle! .Close . Exercise 10.4.5 Hamiltonian Paths .Close 10.4 Additional NP-Complete Problems 447 . 10.5 Summary of Chapter 10 466 List the key points and ideas covered in Chapter 10 and then compare your list with this section of the book. . Ch 10.4,10.5 pp 447,466-467 -- P!=NP? Why does the book continually reinforce P!=NP when it has not yet been shown conclusively one way or the other? . 10.6 References for Chapter 10 467 . TYPO on Page 468 ref 7 The pages should be "pp. 115-116" .Close 16 . Next .See ./17.html . Notes (Ex): Do as many of the relevant exercises as you have time for. You may work in a team of up to 4 students and hand in one joint solution. Bring to class one written solution to an exercise. This must not be a solution to an exercise marked with an asterisk(*) to earn full credit. One of the authors will be invited to present the solution to the class -- failure will loose points. Students taking CS646 must hand in the solution to an exercise marked with an exclamation mark(!) to earn full credit. (Study): Read & think about the assigned items. Submit one question by selecting the submit button at the top of the web page. To earn complete credit you need to do this at least 90 minutes before the start of class. Hints. Read each section twice -- once the easy bits and then the tough bits. Use a scratch pad and pencil as you read. (Topic): To earn all the possible points you must: turn up on time, not leave early, present work when called upon, and take part in discussions. GJ75::=http://www.csci.csusb.edu/dick/cs546/14.html#GJ75.