Schedule

Date	Meet'g	Study(2 pts)	Bring(5 pts)	Topic(5 pts)	Notes
Mon May 22	15	Chapter 10 sections 10.2, 10.3	Ex	NP-Complete
Wed May 24	16	Chapter 10 sections 10.4, 10.5	Ex	Graph Problems & TSP
Mon May 29	-	-	-	HOLIDAY
Wed May 31	17	Chapter 11 sections 11.1, 11.2, 11.3	Ex	Co-NP & PSPACE

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).

10.4 Additional NP-Complete Problems 447

When you spot an NP-complete problem you change strategies from looking for an elegant algorithm to
• Heuristics -- greedy, genetic, dynamic programming
• Special cases
• Approximations

10.4.1 Describing NP-complete Problems 447

1. Problem::=following,
   Net
   1. Name::string.
   2. Short_name::string.
   3. Given::data defining an instance
   4. Goal::properties defining a solution

   
   (End of Net)
   
   
2. NP_Problem::=following,
   Net
   1. Problem.
   2. Proved_NP by: explanation that typically includes the short_name of another NP problem.

   
   (End of 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.

3. 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 ).

4. IS::=Find independent sets in a undirected graph.
   
   • 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.

   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

   ---

   1. Prove IS is NP by constructing polynomial time NTM to solve IS.
   2. Prove IS is NP-hard...
      
      1. 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?
         
         1. Map the 3-CNF into a graph
         2. Each node models a literal in the formula.
         3. The nodes in the IS reflect true literals.
         4. Note. The nodes outside the IS model literals that can be true or false.
         5. Each clause is modeled as a cycle of 3 nodes.
         6. Complements are modeled by adding arcs.
         7. Setting the threshold k = m is vital. Because this makes sure that one literal in each clause is selected.
         8. The triangle of arcs for clause means that a literal is not chosen twice.
         
         
      2. Prove: If E is satisfiable then there is an IS in G of size K.
      3. Prove: If there is an IS in G of size K then E is satisfiable.
      
      

   ---

   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?

5. NC::=the node cover problem, ...
   
   • 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.

   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

   ---

   1. NC is NP
      
      1. Guess a set of k nodes.
      2. Check to see if every edge in G has at least one end in the set.
      
      
   2. Reduce IS to NC
      
      
      Let
      1. G+k be an instance of IS with n nodes
      2. Construct instance of NC with k= n-k.
      
      (Close Let )
      
      1. Proof
         
         1. If...
         2. Only if...
         
         
      
      

   ---

   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.

6. 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:

7. (n1, n2, n3, ....., n[k], n[k+1] = n1) where for all i:1..k, {n[i], n[i+1]} is an edge).

8. 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:

9. (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.

   
   

   • 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 [ $HC ] below.

   Exercise 0 points -- Does your 6 node graph have a Hamiltonian circuit?

   Special case of TSP: all edges have same length = 1.

   
   

   • 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.

   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
   
   1. DHC is NP -- easy!
   2. Reduce 3SAT to DHC

      ---

      1. many details and gadgets

      ---

   3. Proof of simulation
      
      1. if
      2. only-if
      
      
   
   

   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

10. HC::problem=following,
    
    • 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.

    Theorem 10.23 HC is NP-complete

    Structure of Proof
    
    1. HC is NP -- OMITTED
    2. Reduce DHC to HC
       
       1. 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!
       2. Proof
          • if
          • only-if
       
       
    
    

11. TSP::=following
    
    • 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

    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.

    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!

    Exercise 10.4.5 Hamiltonian Paths

. . . . . . . . . ( end of section 10.4 Additional NP-Complete Problems 447) <<Contents | End>>

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"

. . . . . . . . . ( end of section 16) <<Contents | End>>

Next