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