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

27 views2 pages
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)
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.