Scribd Logo
Upload

Welcome to Scribd!

  • 420 views

    Solution To CS 5104 Take-Home Quiz

    Uploaded by

    khawarbashir
    This document contains the solution to a CS 5104 take-home quiz with 3 questions. Question 1 shows that the ≤P relation is transitive for languages by constructing a polynomial-time reduction from L1 to L3 given reductions from L1 to L2 and L2 to L3. Question 2 involves filling out a table for a polynomial time algorithm for context-free language recognition. Question 3 proves that the DOM-SET problem is NP-complete by giving a polynomial-time reduction from the known NP-complete VERTEX-COVER problem to DOM-SET.

    Copyright:

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

    Solution To CS 5104 Take-Home Quiz

    Uploaded by

    khawarbashir
    420 views2 pages
    This document contains the solution to a CS 5104 take-home quiz with 3 questions. Question 1 shows that the ≤P relation is transitive for languages by constructing a polynomial-time reduction from L1 to L3 given reductions from L1 to L2 and L2 to L3. Question 2 involves filling out a table for a polynomial time algorithm for context-free language recognition. Question 3 proves that the DOM-SET problem is NP-complete by giving a polynomial-time reduction from the known NP-complete VERTEX-COVER problem to DOM-SET.

    Original Title

    quiz_solution_2006-04-20

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains the solution to a CS 5104 take-home quiz with 3 questions. Question 1 shows that the ≤P relation is transitive for languages by constructing a polynomial-time reduction from L1 to L3 given reductions from L1 to L2 and L2 to L3. Question 2 involves filling out a table for a polynomial time algorithm for context-free language recognition. Question 3 proves that the DOM-SET problem is NP-complete by giving a polynomial-time reduction from the known NP-complete VERTEX-COVER problem to DOM-SET.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    420 views2 pages

    Solution To CS 5104 Take-Home Quiz

    Uploaded by

    khawarbashir
    This document contains the solution to a CS 5104 take-home quiz with 3 questions. Question 1 shows that the ≤P relation is transitive for languages by constructing a polynomial-time reduction from L1 to L3 given reductions from L1 to L2 and L2 to L3. Question 2 involves filling out a table for a polynomial time algorithm for context-free language recognition. Question 3 proves that the DOM-SET problem is NP-complete by giving a polynomial-time reduction from the known NP-complete VERTEX-COVER problem to DOM-SET.

    Copyright:

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

    CS 5104 take-home quiz -1- April 20, 2006

    Solution to CS 5104 Take-home quiz

    1. (5 points) Show that the ≤P relation is a transitive relation on languages. That is, show
    that if L1 ≤P L2 and L2 ≤P L3, then L1 ≤P L3.

    Let M1 be a polynomial-time TM that reduces L1 to L2


    Let M2 be a polynomial-time TM that reduces L2 to L3
    Construct M = On input w:
    Run M1 on w to get w′
    Run M2 on w′ to get w′′
    Output w′′

    The runtime of M is polynomial in size |w|.

    w ∈ L1 ⇔ w′ ∈ L2 ⇔ w′′ ∈ L3

    Therefore, M is a polynomial-time TM that reduces L1 to L3

    2. (5 points) Fill out the table described in the polynomial time algorithm for context-
    free language recognition from Theorem 7.16 for string w = baba and CFG G:

    S → RT
    R → TR | a
    T → TR | b

    last symbol
    b a b a
    b {T} { R, T } {S} { S, R, T }
    first a {R} {S} {S}
    symbol b {T} { R, T }
    a {R}
    CS 5104 take-home quiz -2- April 20, 2006

    3. (15 points) A subset of the nodes of graph G is a dominating set if every node of G is
    either in the subset or is adjacent to some node in the subset. Let

    DOM-SET = { 〈G, k〉 | G has a dominating set with k nodes }

    Show that it is NP-complete by giving a reduction from VERTEX-COVER.

    I. DOM-SET ∈ NP
    A. Certificate: a set of vertices that dominate G
    B. Algorithm: M = “On input 〈G, c〉:
    for each vertex v in G
    check if v ∈ c or ∃ x ∈ c such that (v, x) is in G
    C. Runtime: Polynomial in V[G] + E[G]

    II. DOM-SET is NP-hard (we show VERTEX-COVER ≤P DOM-SET


    A. Algorithm: R: 〈G, k〉 → 〈G′, k′〉
    R = “On input 〈G, k〉:
    set k′ = k
    copy all edges and their vertices from G into G′
    // note: this does not copy vertices with no edges
    for each edge (x, y) in G
    add a vertex zx,y to G′
    add edges (x, zx,y) and (y, zx,y) to G′
    B. Runtime: Clearly polynomial
    C. Correctness: Show: 〈G, k〉 ∈ VERTEX-COVER ⇔ 〈G′, k′〉 ∈ DOM-SET
    (⇒)
    Assume G has a vertex cover V of size k
    ⇒ V dominates all vertices that have at least one edge, and
    V dominates all new vertices zx,y added to G′
    ⇒ V dominates G′
    (⇐)
    Assume that G′ has a dominating set D of size k
    ⇒ Let D′ = (D ∩ V[G]) ∪ X where X ⊆ V[G] and x ∈ X if
    1. (x, y) ∈ E[G]
    2. x, y ∉ D ∩ V[G]
    3. y ∉ X
    4. zx,y ∈ D (zx,y ∈ V[G′] – V[G] by R’s construction of G′)
    ⇒ D′ ≤ k (X has ≤ one element for every element of V[G′] – V[G])
    and for all edges (u, v) ∈ G,
    Case 1: u ∈ D ∩ V[G] or v ∈ D ∩ V[G] ⇒ D′ covers (u, v)
    Case 2: u,v ∉ D ∩ V[G] ⇒ zu,v ∈ D ⇒ u or v ∈ X ⇒ D′ covers (u,v)

    You might also like