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

27 views2 pages

Published on 16 Oct 2011

Department

Computer Science

Course

CS341

Professor

CS 341, Winter 2010

Timothy Chan

Assignment 5 (due April 5 Monday noon)

Please read http://www.student.cs.uwaterloo.ca/~cs341/policies.html ﬁrst 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 k≤n.

Output: a partition of Sinto ksubsets S1,...,Skminimizing

k

X

i=1

X

j:aj∈Si

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 K≤n.

Output: a subset S⊆Vof 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

## 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: