Sale!

# CSC373 Tutorial 5

\$30.00

Category:

CSC373
Tutorial 5

Q1 LP and IP
For each problem below, describe how to represent the problem as a linear or integer program,
including a brief justification of your inequalities and an explanation of how solutions to your program correspond to solutions to the original problem.
1. Simple Scheduling with Prerequisites (SSP):
You are given a set of jobs, some of which need to be finished before others (prerequisites). You
need to assign start times to jobs to complete all jobs in the least amount of time. (Note: If there
are circular prerequisites, then there is no feasible solution, and your program should indicate so.)
Formally, you are given n jobs with a list of durations d1, d2, . . . , dn, and a boolean pi,j for every
pair (i, j) of jobs such that if it is true, job i must finish before job j can begin. You need to find
start times s1, s2, . . . , sn for the jobs (no job can start earlier than time 0) that minimize the total
time to complete all jobs, while ensuring each job i finishes no later than the start time of all jobs
j for which i is a prerequisite. Write a linear program for this.
2. Set Cover (SC):
Given a set of elements E = {x1, x2, . . . , xn} and a collection of subsets of E, S = {H1, H2, . . . , Hm},
we want to find the smallest subset C of E such that for each set Hj ∈ S, C ∩ Hj 6= φ. Write an
integer program for this.
Q2 Complexity
Are the following decision problems in P/NP/coNP?
1. TRIANGLE
Input: An undirected graph G = (V, E).
Question: Does G contain a “triangle” (i.e. a subset of three vertices such that there is an edge
between any two of them)?
2. CLIQUE
Input: An undirected graph G = (V, E) and a positive integer k.
Question: Does G contain a k-clique (i.e. a subset of k vertices such that there is an edge between
any two of them)?
3. NON-ZERO
Input: A set of integers S.
Question: Does every non-empty subset of S have non-zero sum?
1
4. HAMILTONIAN-PATH (HP)
Input: An undirected graph G = (V, E).
Question: Does G contain a simple path that includes every vertex?
Q3 Reductions
Consider the Hamiltonian Cycle (HC) problem, which is similar to the HP problem described above.
HAMILTONIAN-CYCLE (HC)
Input: An undirected graph G = (V, E).
Question: Does G contain a simple cycle that includes every vertex?
1. The textbook CLRS shows that HC is is NP-complete (Subsection 34.5.3). Give a reduction
from HC to HP (i.e. HC ≤p HP) to prove HP is also NP-complete.
2. Suppose instead that we knew HP is NP-complete, and wanted to use it to show that HC is
NP-complete. Give a reduction from HP to HC (i.e. HP ≤p HC).
2

CSC373 Tutorial 5
\$30.00
Hello
Can we help?