Scribd Logo
Upload

Welcome to Scribd!

  • 67 views

    NP Complete Reductions

    Uploaded by

    tariqravian
    The document proves that two problems, vertex cover and Hamiltonian path, are NP-complete. It first presents a theorem stating that if a language A is NP-complete and reducible to another language B in polynomial time, then B is also NP-complete. It then uses this to prove vertex cover is NP-complete by showing it is in NP and that 3CNF-SAT reduces to it in polynomial time. A graph representation is given and it is shown that a satisfying assignment corresponds to a vertex cover of a certain size.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd

    NP Complete Reductions

    Uploaded by

    tariqravian
    67 views24 pages
    The document proves that two problems, vertex cover and Hamiltonian path, are NP-complete. It first presents a theorem stating that if a language A is NP-complete and reducible to another language B in polynomial time, then B is also NP-complete. It then uses this to prove vertex cover is NP-complete by showing it is in NP and that 3CNF-SAT reduces to it in polynomial time. A graph representation is given and it is shown that a satisfying assignment corresponds to a vertex cover of a certain size.

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document proves that two problems, vertex cover and Hamiltonian path, are NP-complete. It first presents a theorem stating that if a language A is NP-complete and reducible to another language B in polynomial time, then B is also NP-complete. It then uses this to prove vertex cover is NP-complete by showing it is in NP and that 3CNF-SAT reduces to it in polynomial time. A graph representation is given and it is shown that a satisfying assignment corresponds to a vertex cover of a certain size.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    67 views24 pages

    NP Complete Reductions

    Uploaded by

    tariqravian
    The document proves that two problems, vertex cover and Hamiltonian path, are NP-complete. It first presents a theorem stating that if a language A is NP-complete and reducible to another language B in polynomial time, then B is also NP-complete. It then uses this to prove vertex cover is NP-complete by showing it is in NP and that 3CNF-SAT reduces to it in polynomial time. A graph representation is given and it is shown that a satisfying assignment corresponds to a vertex cover of a certain size.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 24

    More NP-complete Problems

    1
    Theorem: (proven in previous class)

    If: Language A is NP-complete


    Language B is in NP
    A is polynomial time reducible to B

    Then: B is NP-complete

    2
    Using the previous theorem,
    we will prove that 2 problems
    are NP-complete:

    Vertex-Cover

    Hamiltonian-Path

    3
    Vertex Cover
    Vertex cover of a graph
    is a subset of nodes S such that every edge
    in the graph touches one node in S

    Example:

    S = red nodes
    4
    Size of vertex-cover
    is the number of nodes in the cover

    Example: |S|=4

    5
    Corresponding language:

    VERTEX-COVER = { G , k :
    graph G contains a vertex cover
    of size k }

    Example:
    G

    G ,4  VERTEX - COVER


    6
    Theorem: VERTEX-COVER is NP-complete

    Proof:
    1. VERTEX-COVER is in NP
    We have proven this before

    2. We will reduce in polynomial time


    3CNF-SAT to VERTEX-COVER
    (NP-complete)

    7
    Let  be a 3CNF formula
    with m variables
    and l clauses

    Example:
      ( x 1  x 2  x 3 )  (x 1  x 2  x 4 )  ( x 1  x 3  x 4 )
    Clause 1 Clause 2 Clause 3

    m4
    l 3
    8
    Formula  can be converted
    to a graph G such that:

     is satisfied

    if and only if

    G Contains a vertex cover


    of size k  m  2l

    9
      ( x 1  x 2  x 3 )  ( x 1  x 2  x 4 )  (x 1  x 3  x 4 )
    Clause 1 Clause 2 Clause 3
    Variable Gadgets 2m nodes
    x1 x1 x2 x2 x3 x3 x4 x4

    Clause Gadgets 3l nodes


    x1 x1 x1

    x2 x3 x2 x4 x3 x4
    Clause 1 Clause 2 Clause 3
    10
      ( x 1  x 2  x 3 )  ( x 1  x 2  x 4 )  (x 1  x 3  x 4 )
    Clause 1 Clause 2 Clause 3

    x1 x1 x2 x2 x3 x3 x4 x4

    x1 x1 x1

    x2 x3 x2 x4 x3 x4
    Clause 1 Clause 2 Clause 3
    11
    First direction in proof:

    If  is satisfied,
    then G contains a graph of size k  m  2l

    12
    Example:
      (x 1  x 2  x 3 )  ( x 1  x 2  x 4 )  ( x 1  x 3  x 4 )
    Satisfying assignment
    x1  1 x2  0 x3  0 x4  1

    We will show that G contains


    a vertex cover of size
    k  m  2l  4  2  3  10

    13
      ( x 1  x 2  x 3 )  ( x 1  x 2  x 4 )  (x 1  x 3  x 4 )
    x1  1 x2  0 x3  0 x4  1

    x1 x1 x2 x2 x3 x3 x4 x4

    x1 x1 x1

    x2 x3 x2 x4 x3 x4

    Put every satisfying literal in the cover


    14
      ( x 1  x 2  x 3 )  ( x 1  x 2  x 4 )  (x 1  x 3  x 4 )
    x1  1 x2  0 x3  0 x4  1

    x1 x1 x2 x2 x3 x3 x4 x4

    x1 x1 x1

    x2 x3 x2 x4 x3 x4
    Select one satisfying literal in each clause gadget
    and include the remaining literals in the cover 15
    This is a vertex cover since every edge is
    adjacent to a chosen node

    x1 x1 x2 x2 x3 x3 x4 x4

    x1 x1 x1

    x2 x3 x2 x4 x3 x4

    16
    Explanation for general case:

    x1 x1 x2 x2 x3 x3 x4 x4

    Edges in variable gadgets


    are incident to at least one node in cover

    17
    Edges in clause gadgets
    are incident to at least one node in cover,
    since two nodes are chosen in a clause gadget

    x1 x1 x1

    x2 x3 x2 x4 x3 x4

    18
    Every edge connecting variable gadgets
    and clause gadgets is one of three types:

    x1 x1 x2 x2 x3 x3 x4 x4

    x1 x1 x1

    x2 x3 x2 x4 x3 x4

    Type 1 Type 2 Type 3


    All adjacent to nodes in cover 19
    Second direction of proof:

    If graph G contains a vertex-cover


    of size k  m  2l
    then formula  is satisfiable

    20
    Example:

    x1 x1 x2 x2 x3 x3 x4 x4

    x1 x1 x1

    x2 x3 x2 x4 x3 x4

    21
    To include “internal’’ edges to gadgets,
    and satisfy k  m  2l

    exactly one literal in each variable gadget is chosen


    x1 x1 x2 x2 x3 x3 x4 x4
    m chosen out of 2m

    exactly two nodes in each clause gadget is chosen


    x1 x1 x1

    x2 x3 x2 x4 x3 x4

    2l chosen out of 3l
    22
    For the variable assignment choose the
    literals in the cover from variable gadgets

    x1 x1 x2 x2 x3 x3 x4 x4

    x1  1 x2  0 x3  0 x4  1

      (x 1  x 2  x 3 )  ( x 1  x 2  x 4 )  ( x 1  x 3  x 4 )

    23
      (x 1  x 2  x 3 )  ( x 1  x 2  x 4 )  ( x 1  x 3  x 4 )
    is satisfied with
    x1  1 x2  0 x3  0 x4  1

    x1 x1 x2 x2 x3 x3 x4 x4

    x1 x1 x1

    x2 x3 x2 x4 x3 x4

    since the respective literals satisfy the clauses


    24

    You might also like