12 November 2015 Term Test # 2 — Sample Solutions CSC 373 H1
Note to Students: This file contains sample solutions to the term test together with the marking scheme and comments for each question. Please read the solutions and the marking schemes and comments carefully. Make sure that you understand why the solutions given here are correct, that you understand the mistakes that you made (if any), and that you understand why your mistakes were mistakes.
Remember that although you may not agree completely with the marking scheme given here it was followed the same way for all students. We will remark your test only if you clearly demonstrate that the marking scheme was not followed correctly.
For all remarking requests, please submit your request in writing directly to your instructor. For all other questions, please don’t hesitate to ask your instructor during office hours or by e-mail.
Question1. [9marks]
Recall the Maximum Bipartite Matching problem: given an undirected bipartite graph G = (V1,V2,E), where E ⊆ V1 × V2, find a subset of disjoint edges with maximum size (where two edges are disjoint if they have no common endpoint).
Give a linear (or integer) program that corresponds to this problem. Describe clearly every component of your answer. Then, justify the correctness of your linear program: explain clearly what each variable and constraint represents and how solutions to each problem correspond to each other (and what that tells you about the relative values of those solutions).
Hint: Use one variable for each edge. If you are unable to solve this problem, you can get more than 10% of the marks by explaining clearly what your solution should consist of (including how to argue its correctness).
Sample Solutions:
Let V1 = {u1,…,uk} and V2 = {w1,…,w}.
Variables: xi,j for all i,j with (ui,wj) ∈ E — intention: matching M = (ui,wj) : xi,j = 1
Objective Function: maximize x — equal to |M| (ui,wj)∈E i,j
page 1 of 3
over…
Constraints: xi,j ∈ {0,1}, for all (ui,wj) ∈ E
x 1,foreachu ∈V i,j i 1
no two edges in M have acommonendpoint
wj ∈V2:(ui ,wj )∈E
ui∈V1:(ui,wj)∈E i,j j 2
x 1,foreachw ∈V
Every matching M over G gives rise to a feasible solution by setting xi,j = 1 iff (ui,wj) ∈ M: since no two edges share an endpoint, every constraint is satisfied. Moreover, the size of M is equal to the value of the objective function, so the maximum value of the objective function is at least as large as the size of the maximum matching.
Every feasible solution to the integer program yields a matching M by selecting every edge (ui,wj) such that xi,j = 1: the contraints guarantee that no two edges share an endpoint and the value of the objective is equal to the size of M. So the size of the maximum matching is at least as large as the maximum value of the objective function.
Alternative Solution:
Variables: xi,j forall1ik=|V1|,1j=|V2| Objective Function: maximize k x
i=1 j=1 i,j Constraints: xi,j ∈{0,1}foralli,j
xi,j =0foralli,jsuchthat(ui,wj)E j=1xi,j 1fori=1,…,k
ki=1 xi,j 1 for j = 1,…,
CSC 373 H1 Term Test # 2 — Sample Solutions
12 November 2015
Question2. [8marks]
Consider the network N1 pictured on the right. Part(a) [3marks]
Compute the capacity of the cut X1 = {s,b,c},{a,d,t}. Show your work: list the components of the network used to obtain your answer.
Sample Solutions:
c(X1) = c(s, a) + c(c, a) + c(c, t) + c(c, d) + c(s, d) =10+3+8+3+5=29
s
a
10 3 3 5
8 b 10 c 8 t
5 3 3 10
d
Part(b) [1mark]
Let C1 represent your answer to Part (a). What can you conclude about |f |, for all valid flows f over N1? Sample Solutions:
|f|C1 (or|f|29) Part(c) [4marks]
Given one network N and one cut X = (S , T ) in N , suppose that we reduce the capacity of every forward edge across X. Does the maximum flow value in N necessarily decrease? Justify your answer.
Sample Solutions:
24
No: consider network N = s −→ a −→ t and cut X = {s,a},{t} . If we reduce the
′23 capacityofeveryforwardedgeacrossXby1,theresultingnetworkN =s−→a−→t
still has the same maximum flow value as N. Question3. [8marks]
For each of the following decision problems D, state whether D ∈ P, D ∈ NP or D ∈ coNP—make the strongest claim that you can. Then, justify your answer by writing down an explicit algorithm for D and explaining why it satisfies the properties required for your answer. Do not attempt to justify that other complexity classes are incorrect; focus on providing evidence that your choice is correct.
Part(a) [4marks] SomeShortPaths (“SSP” for short)
Input: UndirectedgraphG=(V,E),verticess,t∈V,non-negativeintegerk|V|.
Output: Does G contain some simple path from s to t with no more than k edges on the path?
Sample Solutions:
SSP ∈ P. On input G = (V,E), s,t ∈ V, k |V|:
run BFS in G starting from s
let be the number of edges on the path from s to t found by BFS return k
Because BFS is known to find a path with the minimum number of edges, the algorithm returns True iff G contains a simple path from s to t with at most k edges. Moreover, BFS runs in polytime so the entire algorithm is polytime.
page 2 of 3 cont’d. . .
12 November 2015 Term Test # 2 — Sample Solutions CSC 373 H1
Part(b) [4marks] AllShortPaths (“ASP” for short)
Input: UndirectedgraphG=(V,E),verticess,t∈V,non-negativeintegerk|V|. Output: Does every simple path in G from s to t contain no more than k edges?
Sample Solutions:
ASP ∈ coNP. On input G = (V,E), s,t ∈ V, k |V|, c:
# where c is a sequence of edges from G
check that c represents a simple path in G from s to t return len(c) > k
Clearly, the algorithm runs in polytime. Moreover, it outputs True for some value of certificate c iff there is some simple path in G from s to t with more than k edges, iff G , s, t, k is a no-instance.
(Note: It’s acceptable to invert the output of the verifier.)
page 3 of 3 end