Assignment # 3

CSC 373H1

Worth: 10%

1. [20 marks]

An epidemiologist is studying the transmission of the COVID-19 virus in the Greater Toronto Area

(GTA). The community is represented by a graph G = (V,E) where vertices represent people in the

GTA and edges represent two individuals who have interacted with each other. To study how the

virus may have spread, the epidemiologist wants to know if people in the GTA can be divided into at

most k groups G1,…,Gk where:

• Everyone in V is in some group, and no person is in two di↵erent groups.

• Everyone in group Gi has interacted with each other.

(a) [5 marks] Show that the above problem given the graph G and integer k as inputs is in NP.

(b) [5 marks] Show that the above problem when k 2 is decidable in polynomial time.

(c) [10 marks] Show that the above problem when k 3 is NP-Complete.

2. [20 marks]

Consider the following DisjointHamiltonianPaths decision problem (“DHP” for short).

• Input: Graph G = (V,E) — G may be directed or undirected.

• Output: Does G contain at least two edge-disjoint Hamiltonian paths?

(Two paths are said to be edge-disjoint if there is no edge that belongs to both paths.)

(a) [12 marks] Write a detailed proof that DisjointHamiltonianPaths is NP-complete. State what

you are doing at each step of your solution: it will be graded on its structure as much as on its

content.

(b) [8 marks] Give a precise definition for the DisjointHamiltonianPaths-Search problem. Then,

write a detailed argument that this problem is polynomial-time self-reducible. Once again,

your solution will be graded on its structure as well as its content, so make sure to state what

you are doing at each step.

3. [20 marks]

A propositional formula ‘ is in 3-Positive Conjunctive Normal Form (3-PCNF) i↵ it is written

in 3-CNF with no negative literal, i.e., all the variables in the formula are positive. For example,

‘ = (x1 _x3 _x4)^(x2 _x3 _x2)^(x1 _x2 _x3) is in 3-PCNF. Obviously ‘ is satisfiable by setting all

the variables to True.

We are interested in a di↵erent question: how few variables must be set to True in order to satisfy ‘?

For example, the previous formula can be satisfied by setting just one variable to True, namely, x3.

This is an NP-Hard problem (you do not need to prove this).

(a) [8 marks] Define the corresponding Decision Problem for this optimization problem, and show

that this optimization problem is polynomial-time self-reducible.

(b) [12 marks] Formulate the optimization problem as an integer program. Using this, derive a

polynomial-time 3-approximation algorithm for the same. That is, if the minimum number of

variables needed to be set to True to make ‘ satisfiable is k⇤

, your algorithm should set at most

3k⇤ variables to True. Provide a proof of correctness of your algorithm and compute its time

complexity.

1 Page 1 of 2

Dept. of Computer Science

University of Toronto

Assignment # 3

(Due August 14, 11:59 pm)

CSC 373H1

Summer 2021

4. [20 marks]

Your friends want to break into the lucrative co↵ee shop market by opening

a new chain called The Co↵ee Pot. They have a map of the street corners in

a neighbourhood of Toronto (shown on the right), and estimates pi,j of the

profits they can make if they open a shop on corner (i,j), for each corner.

However, municipal regulations forbid them from opening shops on corners

(i 1, j), (i + 1, j), (i,j 1), and (i,j + 1) (for those corners that exist) if they

open a shop on corner (i,j). As you can guess, they would like to select street

corners where to open shops in order to maximize their profits! (1,1) (1,2) ··· (1,n)

···

(2,1) (2,2) ··· (2,n)

.

.

. .

.

. ··· .

.

.

(m,1) (m,2) ··· (m,n)

(a) [5 marks] Consider the following greedy algorithm to try and select street corners.

C := {(i,j):1 i m,1 j n} # C is the set of every available corner

S := ; # S is the current selection of corners

while C , ;:

pick (i,j) 2 C with the maximum value of pi,j

# Add (i,j) to the selection and remove it (as well as all corners adjacent to it) from C.

S := S [{(i,j)}

C := C {(i,j),(i 1, j),(i + 1, j),(i,j 1),(i,j + 1)}

return S

Give a precise counter-example to show that this greedy algorithm does not always find an

optimal solution. State clearly the solution found by the greedy algorithm, and show that it is

not optimal by giving another selection with larger profit.

(b) [15 marks] Prove that the greedy algorithm from part (a) has an approximation ratio of 4. (Hint:

Let S be the selection returned by the greedy algorithm and let T be any other valid selection of

street corners. Show that for all (i,j) 2 T , either (i,j) 2 S or there is an adjacent (i0

, j0

) 2 S with

pi0,j0 pi,j. What does this means for all (i,j) 2 S and their adjacent corners?)

2 Page 2 of 2