Skip to main contentCal State San Bernardino
>> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CS546/646] >> 16 [Text Version]
[About] [Contact] [Grades] [Projects] [Submit] [Schedule] [Syllabus] [Search ]
Session: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] (16) [17] [18] [19] [20]
Thu Jun 8 13:03:01 PDT 2006




      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


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


        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

            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


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


    [ 17.html ]


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

  1. GJ75::= See

    Standard Definitions

  2. FSA::="Finite State Acceptor/Automata", a theoretical machine with a finite set of states.
  3. ND::="Non-deterministic", a machine that can try out many possibilities and always guesses the right choice. Note: For a given problem a ND solution is simpler and easier to understand than a deterministic one. We study ND machines to discover how to use them as high-level designs for more complicated deterministic machines. Plus it's fun.
  4. PDA::="Push down Automata", a machine with a finite control and a single stack for remembering intermediate data. Kind of like half a TM.
  5. RJB::=The author of this document, [ ../index.html ]
  6. |-RJB="Richard J Botting, Comp Sci Dept, CSUSB".
  7. Schedule::= See
  8. Search::= See
  9. Syllabus::= See, and also see [ syllabus.html ] (my generic syllabus).
  10. TBA::="To Be Announced".
  11. TM::="Turing Machine".
  12. NTM::="Nondeterministic Turing Machine".
  13. nondeterministic::="A machine that can make choices as it runs and accepts an input iff any sequence of choices leads to acceptance."
  14. DTM::="Deterministic Turing Machine".
  15. runtime::=run_time,
  16. run_time::="The number of steps a TM takes before it halts when start on a given input".
  17. complexity::="The largest run_time for any word with a given length" , usually expressed as an assymptotic (Big-O) formula.
  18. P::@problem=class of problems that a DTM can compute in polynomial_time.
  19. NP::@problem=class of problems that a NTM can compute in polynomial_time.
  20. polynomial_time::=An algorithm/TM is said to halt in polynomial time if the number of steps given n items of data is less than O(n^c) for some constant c.

    From Logic

  21. LOGIC::= See

  22. (LOGIC)|- (ei): Existential instantiation -- if P is true of something then we can substitute a new variable for it.
  23. (LOGIC)|- (eg): existential generalization -- if P is true of this thing then it is true of something!
  24. (LOGIC)|- (given): a proposition that is assumed as part of a Let...End Let argument. Typically if A and B and C then D starts with assuming A,B, and C are given. They are called the hypotheses.
  25. (LOGIC)|- (goal): a proposition that we wish to prove. Typically the part after the then in an if...then... result. This is called the conclusion.
  26. (LOGIC)|- (def): By definition of a term defined above.
  27. (LOGIC)|- (algebra): Either by using well known algebraic results, or by use a series of algebraic steps.
  28. (LOGIC)|- (RAA): Reduce to absurdity. The end of a Let/Po/Case/Net that establishes the negation of the last set of assumptions/hypotheses.