Homework Assignment 3

Due: by 2pm on Web 26 Nov
Worth: 8%

For each question, please write up detailed answers carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

WARNING! Some browsers do not display the "complement" notation (overline) properly, e.g., "the complement of L is denoted L". If the second "L" in this sentence does not display with a bar on top, then please consult the ASCII version of the handout to make sure you can read the questions correctly.

  1. A "core set" in an undirected graph G = (V,E) is a subset of vertices C ⊆ V such that there is no edge between any two vertices of C (i.e., ∀ u,v ∈ C, (u,v) ∉ E), and every vertex outside C has an edge to some vertex within C (i.e., ∀ u ∈ V-C, ∃ v ∈ C, (u,v) ∈ E).

    For example, consider the graph G = (V,E) with V = {a,b,c,d,e,f} and E = { (a,b), (a,d), (a,f), (c,d), (c,e), (d,e), (e,f) }.

    • The set {a,d} is not a core set because of the presence of edge (a,d) — even though it is the case that every vertex from {b,c,e,f} has an edge to a or d.
    • The set {b,f} is not a core set because d does not have an edge to either b or f — even though there is no edge between b and f.
    • The set {b,c,f} is a core set — none of the edges (b,c), (b,f), or (c,d) belong to the graph, and every vertex in {a,d,e} has an edge to one of b, c, or f.

    Prove that the following language is NP-complete.

    CS (Core Set) = { <G,k> : G is an undirected graph and k is a positive integer such that G contains some core set of size k }

    Hint: Use a reduction from 3SAT for part of your answer.

  2. Define DP = { A ⊆ Σ* : A = B - C for some languages B, C ∈ NP } (recall that B - C = B ∩ C).

    1. Prove that the following language is complete for DP (with respect to ≤p), i.e., for all A ∈ DP, A ≤p CNC.

      CNC (Clique-No-Clique) = { <G1,k1,G2,k2> : G1, G2 are undirected graphs and k1, k2 are positive integers such that G1 contains some clique of size k1 and G2 does not contain any clique of size k2 }

    2. Prove that the following language is also complete for DP — you may make use of the result from part (a).

      MC (Max-Clique) = { <G,k> : G is an undirected graph and k is a positive integer such that the largest clique in G has size exactly k }

  3. Consider the following "Core Set" search problem (see Question 1).

    Input: An undirected graph G and a positive integer k.
    Output: A core set of G of size k, if such a set exists (the special value "None" otherwise).

    Prove that the Core Set problem is polytime self-reducible — include a careful argument that your algorithm works correctly and runs within the required time bound.

  4. For each language L below, state whether L ∈ P, L is NP-complete, or L is coNP-complete (meaning L is NP-complete), then prove your claim.

    1. SumGap = { <S,B,C> : S = {x1,...,xn} is a set of positive integers and B and C are positive integers such that no subset of S has a sum between B and C (i.e., for all S' ⊆ S, either ∑x ∈ S' x < B or ∑x ∈ S' x > C) }

    2. NoLargeSum = { <S,B> : S = {x1,...,xn} is a set of positive integers such that no subset of S has sum greater than B (i.e., for all S' ⊆ S ∑x ∈ S' x ≤ B) }

    3. EasySAT = { <F,k> : F is a propositional formula and k is a positive integer such that there is some assignment of values to the variables of F that makes F true by setting at most k variables to true }

    4. NoLargeCycles = { <G,k> : G is an undirected graph that does not contain any simple cycle on k or more vertices (a cycle is "simple" if it does not repeat any vertex) }

      (For this part, you may not assume that the Hamiltonian Cycle problem is NP-complete, though you may assume that the Hamiltonian Path problem is NP-complete.)