===========================================================================
CSC 363                    Homework Assignment 3                  Fall 2008
===========================================================================

Due: by 2pm on Wed 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.


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 (_ \Sigma* : A = B - C for some languages B, C (- NP }
    (recall that B - C = B n ~C).

    (a) 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) = { <G_1,k_1,G_2,k_2> : G_1, G_2 are
                undirected graphs and k_1, k_2 are positive integers such
                that G_1 contains some clique of size k_1 and G_2 does
                *not* contain any clique of size k_2 }

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

    (a) SumGap = { <S,B,C> : S = {x_1,...,x_n} 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
            \sum_{x (- S'} x < B or \sum_{x (- S'} x > C) }

    (b) NoLargeSum = { <S,B> : S = {x_1,...,x_n} is a set of positive
            integers such that no subset of S has sum greater than B (i.e.,
            for all S' (_ S, \sum_{x (- S'} x <= B) }

    (c) 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 }

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