Homework Assignment 3

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.

    1. L1 = { <G> : G is an undirected graph that contains a simple cycle on no more than n/2 of its vertices }

    2. L2 = { <G> : G is an undirected graph that contains a simple cycle on at least n/2 of its vertices }

    3. L3 = { <S,t> : S = {x1,...,xn} is a nonempty 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., ∑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 R1 = {a,b}, R2 = {b,c}, R3 = {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 ∩ Ri ≠ ∅ for 1≤i≤m). Consider the following related problems.

    BOTTLENECK (BN for short) = { <S, R1, ..., Rm, k> : S is a set of system resources, R1, ..., Rm are process resource requirements (each Ri 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 ∩ Ri ≠ ∅ for 1≤i≤m }

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

    1. Prove that BN is NP-complete.

    2. 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 }