===========================================================================
CSC 363                    Homework Assignment 3                Winter 2008
===========================================================================

Due: by 6pm on Wed 2 Apr
Worth: 8%

For each question, please write up your answer 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.  For each language L below, state whether L (- P or L is NP-complete,
    then prove your claim.  In your answers, you may only make use of
    languages shown to be NP-complete in class or in the textbook.

    (a) L_1 = { <G> : G is an undirected graph that contains a simple cycle
                      on *no more than* n/2 of its vertices }

    (b) L_2 = { <G> : G is an undirected graph that contains a simple cycle
                      on *at least* n/2 of its vertices }

    (c) L_3 = { <S,t> : S = {x_1,...,x_n} is a set of *positive* integers
                        that contains some subset S' (_ S with *at least*
                        n/2 integers (i.e., |S'| >= n/2) and whose sum is
                        equal to t (i.e., \sum_{x (- S'} x = t) }


2.  Consider a system where multiple processes can execute concurrently,
    but where each process requires the exclusive use of one or more system
    resource(s) in order to execute.  It may be impossible to execute more
    than one process at a time because of conflicting resource needs.  For
    example, if the system resources are S = {a,b,c} and there are three
    processes with requirements R_1 = {a,b}, R_2 = {b,c}, R_3 = {c,a}, then
    no two processes can execute at the same time.
    We are interested in identifying "bottlenecks" in such a system, i.e.,
    subsets of the system resources B (_ S such that B intersects with each
    process requirement (B n R_i != {} for 1<=i<=m).  Consider the
    following related problems.

        BOTTLENECK (BN for short) = { <S,R_1,...,R_m,k> : S is a set of
            system resources, R_1,...,R_m are process resource requirements
            (each R_i is a nonempty subset of S), and k is an integer such
            that there is some bottleneck B of size k -- i.e., some B (_ S
            such that B n R_i != {} for 1<=i<=m }

        MIN-BOTTLENECK (MIN-BN for short): On input <S,R_1,...,R_m> (as
            above), return a bottleneck with the smallest possible size.

    (a) Prove that BN is NP-complete.

    (b) Prove that MIN-BN is polytime self-reducible.  (Make sure you
        understand exactly what this question is asking, and the steps
        required to answer it correctly!)


3.  Prove that the following language is NP-complete.  Again, use only
    known NP-complete languages from class or the textbook.

        ZERO-CYCLE (ZC for short) = { <G> : G is an undirected graph
            with non-zero (positive or negative) integer weights w(e) for
            each edge e, and G contains some simple cycle whose total
            weight is zero }