Assignment #5 This is the fifth assignment from winter 2010 term

27 views2 pages
user avatar
Published on 16 Oct 2011
School
University of Waterloo
Department
Computer Science
Course
CS341
CS 341, Winter 2010
Timothy Chan
Assignment 5 (due April 5 Monday noon)
Please read http://www.student.cs.uwaterloo.ca/~cs341/policies.html first for general in-
structions.
1. [12 marks] Turn each of the following optimization problems into a decision problem and
show that the corresponding decision problem is in NP.
(a) [6 marks]
Input: a set Sof nnumbers a1,...,anand an integer kn.
Output: a partition of Sinto ksubsets S1,...,Skminimizing
k
X
i=1
X
j:ajSi
aj
2
.
[Note: the subsets do not have to be contiguous blocks, so the problem is different from
A4Q2!]
(b) [6 marks]
Input: an undirected graph G= (V, E) with nvertices and an integer Kn.
Output: a subset SVof minimum size such that the subgraph Hformed
by removing the vertices of Sand their incident edges from Gdoes not have
connected components of size more than K.
2. [14 marks] Consider the decision problem 4-IS:
Input: An undirected graph G= (V, E) of maximum degree at most 4 and an
integer K.
Output: “yes” iff there exists a subset Sof size at least Ksuch that for every
u, v S, we have uv 6∈ E(i.e., Sis an independent set).
and the decision problem 3-IS:
Input: An undirected graph G= (V, E) of maximum degree at most 3 and an
integer K.
Output: “yes” iff there exists a subset Sof size at least Ksuch that for every
u, v S, we have uv 6∈ E(i.e., Sis an independent set).
Give a polynomial-time reduction from 4-IS to 3-IS. Prove correctness of your reduction.
[Hint: replace each vertex in the old graph with 3 vertices (forming a path of length 2) in the
new graph. . . What should the new Kbe?]
3 bonus marks: give a polynomial-time reduction from IS (the general independent set deci-
sion problem without degree restrictions) to 3-IS. (This implies that 3-IS is NP-complete.)
1
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in

Document Summary

Please read http://www. student. cs. uwaterloo. ca/~cs341/policies. html rst for general in- structions: [12 marks] turn each of the following optimization problems into a decision problem and show that the corresponding decision problem is in np. (a) [6 marks] Input: a set s of n numbers a1, . , an and an integer k n. Output: a partition of s into k subsets s1, . [note: the subsets do not have to be contiguous blocks, so the problem is di erent from. Input: an undirected graph g = (v, e) with n vertices and an integer k n. Input: an undirected graph g = (v, e) of maximum degree at most 4 and an integer k. Output: yes i there exists a subset s of size at least k such that for every u, v s, we have uv (cid:54) e (i. e. , s is an independent set). and the decision problem 3-is: