Combinatorial and Graph Algorithms Dec.

2, 2014
National University of Singapore CS5234
Seth Gilbert Final Exam

Final Exam
• Do not open the exam until you are directed to do so.

• Read all the instructions first.

• The exam contains four problems. You have 120 minutes to earn 100 points.

• The exam contains 18 pages, including this one and 4 pages of scratch paper.

• The exam is closed book. You may bring two double-sided sheet of A4 paper to the exam.
(You may not bring any magnification equipment!) You may not use a calculator, your mobile
phone, or any other electronic device.

• Write your solutions in the space provided. If you need more space, please use the scratch
paper at the end of the midterm. Do not put part of the answer to one problem on a page
for another problem.

• Read through the problems before starting. Do not spend too much time on any one problem.

• Show your work. Partial credit will be given. You will be graded not only on the correctness
of your answer, but also on the clarity with which you express it. Be neat.

• You may use any algorithm given in class without restating it—simply give the name of the
algorithm and the running time. If you change the algorithm in any way, however, you must
provide complete details.

• Good luck!

Problem # Name Possible Points Achieved Points

1 Drawing Pictures 20
2 Short Answer 10
3 Edge-Dominating Set 30
4 Spacely Sprockets 20
5 Startups 101 20

Total: 100

Matric. Num.:
CS5234 Final Exam Matric. No.:

Problem 1. (Drawing pictures) [20 points]

(a) [4 points] Draw a graph that is not a planar graph. Give a proof that your graph is
not planar.

2
CS5234 Final Exam Matric. No.:

(b) [9 points] Execute the Push-Relabel algorithm for three steps on the following graph.
(Note that one step consists of either a push or a relabel ). Fill in the table below identifying
each step, indicating whether each operation is a relabel, a saturating push, or a non-
saturating push. Clearly draw the final state of the graph on the picture, indicating the
result of each operation.

h=1 h=1
8/8
A B

9/9 1/5 6/6

3/3

h=6
10/10 6/6
s C t
h=1 h=0
0/7
3/3 0/4

D
h=1

Step Node/Edge Type (saturating push/non-saturating push/relabel)

3
CS5234 Final Exam Matric. No.:

(c) [7 points] Identify the minimum cost st-cut in the following graph. Prove that the
cut you have identified is the minimum cost cut.

8
A B

9 5 6
3

10 6
s C t
7
3 4

4
CS5234 Final Exam Matric. No.:

Problem 2. (Short Answer ) [10 points]

(a) [5 points] Let G be an arbitrary flow network, and let f be a maximum flow for G.

True or false: there always exists an edge e such that increasing the capacity on e increases
the maximum feasible flow in the network. Explain your answer.

(b) [5 points] Let G be an arbitrary weighted, bipartite graph, and let M be a maximum
weight matching.

True or false: if every edge in G has its value increased by a constant c, then is M still a
maximum weight matching? Explain your answer.

5
CS5234 Final Exam Matric. No.:

Problem 3. (Edge-Dominating Set) [30 points]

Consider the problem of finding an Edge-Dominating Set: Given a connected, unweighted

graph G = (V, E), a set of edges D ✓ E is an edge-dominating set if, for every edge e 2 E,
either: (i) e 2 D, or (ii) some e0 2 D where e0 and e are both adjacent to a shared vertex v.
The goal is to find the minimum sized edge-dominating set.

Here is an example of an edge-dominating set. The thick edges are in the dominating set D,
while the dashed edges are dominated:

6
CS5234 Final Exam Matric. No.:

(a) [6 points] Consider the following attempt to solve the problem of a minimum edge-
dominating set by linear programming. For every edge e, let edges(e) be the set of edges
adjacent to e. For each edge e, we instantiate a variable xe which indicates whether or not
edge e is in the edge-dominating set.
X
min xe (1)
e2E
X
xj 1 8e 2 E (2)
j2edges(e)[e

xe (1 xe ) = 0 8e 2 E (3)
xe  1 8e 2 E (4)
xe 0 8e 2 E (5)

Line (2) is intended to ensure that every edge is dominated by some edge in the dominating
set. Line (3) is intended to ensure that each edge is either included or excluded from the
dominating set. Lines (4) and (5) ensure that each xe is between 0 and 1.

Does this strategy work? Either prove that you can use an LP solver to find the minimum
edge-dominating set, or explain why you cannot use this strategy.

7
CS5234 Final Exam Matric. No.:

(b) [12 points] Consider the following heuristic for constructing an edge-dominating set
for a connected graph G = (V, E):

a. Choose an arbitrary, fixed root node r 2 V .

b. Let T be a spanning tree of G rooted at r constructed via depth-first search.
c. If T has depth 1, then add any arbitrary edge in T to D and return D.
d. Otherwise, let D be the set of edges in T that are not adjacent to a leaf in T .
e. Return D as the edge-dominating set.

Prove that this heuristic returns a correct edge-dominating set (i.e., one in which every
edge is dominated by some edge in the set).

8
CS5234 Final Exam Matric. No.:

(c) [12 points] Prove that the heuristic above returns a 6-approximation of the minimum-
sized edge-dominating set. (A better approximation ratio may be possible, but is not neces-
sary here.)

9
CS5234 Final Exam Matric. No.:

Problem 4. (Spacely Sprockets) [20 points]

(a) [10 points] Spacely Sprockets produces four types of sprockets: A, B, C, D. Making
sprockets requires energy, and your job is to minimize the energy used. Here are the rules:
• Sprocket A costs 2 kilowatts to make, sprocket B costs 1 kilowatt, sprocket C costs 1
kilowatt, and sprocket D costs 4 kilowatts.
• Spacely Sprockets has two factories: X and Y . Factory X makes only sprockets of
type A and D, and Factory Y makes only sprockets of type B and C. Spacely has
a contract with the unions promising to make a certain number of sprockets at each
factory every day. At Factory X, he has agreed to make at least 8 sprockets per day
(in total, of either type). At Factory Y , he has agreed to make exactly four sprockets
a day (in total, of either type).
• The number of sprockets of type C should not exceed 4 per day. (Don’t ask why.)
• Lastly, sprockets of type A take up one cubic meter of space, and sprockets of type D
take up four cubic meters of space. Every day, your client Fred requires that you make
enough sprockets of type A and type D to fill up a 12 cubic meters truck.
• For the purpose of this problem, sprockets can be subdivided into smaller pieces. Hence
if you need to produce 0.3357 sprockets of type C, that is doable.

Give a linear program that will solve this problem, minimizing the number of kilowatts
needed. Write your linear program in standard form.

10
CS5234 Final Exam Matric. No.:

(b) [10 points] Give the dual of the linear program from the previous part. (If you did
not succeed in coming up with a linear program for part (a), then for partial credit make
up any linear program with between three and five variables and between three and five
constraints and give the dual of it.)

11
CS5234 Final Exam Matric. No.:

Problem 5. (Startups 101 ) [20 points]

NUS has decided to o↵er a new module on how to start a startup up. On the first day of class,
we divide the students into three groups: (i) the Computer Scientists, (ii) the Engineers,
and (iii) the Business People.

Next, we need to form teams. Each startup team must have exactly one computer scientist,
one engineer, and one business person. (And each person can be on at most one team.)
To accomplish this, each computer scientist p lists the engineers E(p) and the business
people B(p) that he/she is willing to work with. Each engineer and business person p lists
the computer scientists C(p) that he/she is willing to work with. (We assume that every
engineer is willing to work with every business person, and vice versa.)

In this problem, you will give an algorithm for creating the maximum number of teams
possible. (Everyone who is not assigned a team has to drop the class!) Give the most
efficient algorithm you can.

(a) [8 points] Describe your algorithm, briefly. It is recommended that you draw a
picture.

(b) [4 points] What is the (asymptotic) running time of your algorithm?

12
CS5234 Final Exam Matric. No.:

(c) [8 points] Prove that your algorithm is correct.

13
CS5234 Final Exam Matric. No.:

Scratch Paper

15
CS5234 Final Exam Matric. No.:

Scratch Paper

16
CS5234 Final Exam Matric. No.:

Scratch Paper

17
CS5234 Final Exam Matric. No.:

Scratch Paper

18