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

27 views2 pages
School
University of Waterloo
Department
Computer Science
Course
CS341 CS 341, Winter 2010
Timothy Chan
Assignment 5 (due April 5 Monday noon)
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 diﬀerent 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” iﬀ 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” iﬀ 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.