CSC373H1 Midterm Test—Solutions Fall 2019 Question 1. Network Flow [25 marks]
Let N = (V , E) be a network with a set of nodes V and a set of directed edges E with integer capacities. Let F be the maximum flow value in N from node s to node t. Let P be a simple path from s to t in N consisting of k edges, and let N + be the network obtained from N by adding 1 to the capacity of every edge in P .
(a) (5 marks) TRUE/FALSE: The maximum flow value in N + is at least F + 1. (If this is true, argue why. If this is false, provide a counter-example.)
(b) (5 marks) Prove that the maximum flow value in N + may not be exactly F + 1.
(c) (10 marks) What is a tight upper bound on the maximum flow value in N+ in terms of F and k? You must prove that your upper bound always holds. To show that it is tight, you must produce a network in which the maximum flow value in N + exactly matches your upper bound.
(d) (5 marks) Let N − be the network obtained from N by subtracting 1 from the capacity of every edge in P (assume each edge in P had capacity at least 1 in N ). TRUE/FALSE: The maximum flow value in N − is always strictly less than F. (If this is true, argue why. If this is false, provide a counter-example.)
Sample Solution:
(a) TRUE. This is because one can simply take a maximum flow in N with value F, and augment it
along P by one unit in N+ resulting in a flow of value F +1. (b) Consider the following network.
aa
N=s 0/1 t N+=s 0/2 t
bb
In network N , the maximum flow is F = 2. Network N + is obtained by increasing the capacity of every edgeonpaths→a→b→tby1.ThemaximumflowinN+ is4>F+1.
(c) We show that the tight bound is F + ⌊ k+1 ⌋. 2
Upper bound: Take any min-cut (A, B) of network N . By max-flow-min-cut theorem, it has capacity
F. We are interested in edges of P that go from A to B (since the increase in capacity of those edges
can increase the cut capacity). Note that for every A → B edge in P , we must have a subsequent B → A
edge before we can have another A → B edge. Hence, P has at most ⌊ k+1 ⌋ edges going A → B. Hence, 2
when we increase the capacity of each edge in P by 1, the capacity of cut (A, B) increases by at most ⌊ k+1 ⌋. Hence, N + has a cut of capacity at most F + ⌊ k+1 ⌋, so by max-flow-min-cut, its max flow is at
22
most F + ⌊ k+1 ⌋. 2
Lower bound: Consider the network N in the image below. The edges in red are the edges in path P .
The idea is that every edge going from left to right is a bottleneck (it has capacity 1 right now, but
if its capacity increases to 2, it can add a unit flow). Indeed, there are ⌊k+1⌋ edges going from left to 2
right, and increasing all their capacities by 1 increases the max flow precisely by ⌊k+1⌋. 2
page 1 of 3 over…
1/1
1/1
2/2
2/2
1/2
1/2
2/2
2/2
CSC373H1 Midterm Test—Solutions Fall 2019
(d) TRUE. Take any min-cut (A,B) in network N. By max-flow-min-cut, it has capacity F. Since P goes from s ∈ A to t ∈ B, it has at least one edge going from A to B. Since the capacity of this edge is decreasing by 1, the capacity of (A, B) in N − is at most F − 1. Hence, min cut (and thus max flow) in N− isatmostF−1.
Question 2. Integer Linear Programming [20 marks]
Recall that given an undirected graph G = (V , E), we say that G is k-colourable if we can assign a colour c(v) ∈ {1, . . . , k} to every vertex v ∈ V such that no two adjacent vertices have the same colour (i.e. c(u) c(v) for all (u,v) ∈ E). The minimum vertex coloring problem, MinColour, is defined as follows.
• Input: An undirected graph G = (V , E).
• Output: The smallest positive integer k such that G is k-colourable.
We wish to write a binary integer program (with each variable taking value in {0, 1}) to solve MinColour. (a) (5 marks) Argue that the solution of MinColour is never greater than n (the number of nodes in G).
(b) (15 marks) Provide a binary integer linear program to solve MinColour. Clearly explain why your objective minimizes the number of colours used and why your constraints ensure a valid colouring. For full marks, your program should use at most O(n2) binary variables, where n is the number of nodes in G.
Sample Solution:
(a) Giving each node of G a different colour is certainly a valid colouring and uses n colours. Hence,
the minimum number of colours needed is at most n.
(b) We will keep n colours at our disposal (by part (a), these are sufficient). For each possible colour k ∈ {1, . . . , n}, we will use a binary variable yk to indicate whether colour k is used anywhere. For each node i ∈ V and each possible colour k ∈ {1,…,n}, we will use a binary variable xi,k to denote whether node i is given colour k. Given this, the binary IP is as follows. The role of the objective function and each constraint is explained in comments next to it.
Minimize nk=1 yk Such that
nk=1 xi,k = 1,∀i ∈ V
xi,k yk,∀i ∈ V ,k ∈ {1,…,n} xi,k+xj,k 1,∀(i,j)∈E,k∈{1,…,n} xi,k,yk ∈ {0,1},∀i ∈ V ,k ∈ {1,…,n}
#Minimize number of colours used
#Each node gets one colour #Only colours that are used can be assigned #Adjacentnodescannotgetthesamecolour #Binary variables
page 2 of 3 cont’d. . .
CSC373H1 Midterm Test—Solutions Fall 2019 Question 3. P/NP/coNP [10 marks]
(a) (2.5 marks) Does P = N P imply N P = coN P ? Justify your answer.
(b) (2.5 marks) Does N P = coN P imply P = N P ? Justify your answer.
(c) (2.5 marks) Given an undirected graph G and a positive integer k, the k-Colour problem asks whether G is k-colourable (i.e. whether it has a valid colouring using at most k colours). Show that given a polynomial-time algorithm for k-Colour, one can solve MinColour in polynomial time.
(d) (2.5 marks) Show that given a polynomial-time algorithm for MinColour, one can solve k-Colour in polynomial time.
Sample Solution:
(a) Yes. The complement of a problem in P is also in P. Hence, if P=NP, then the complement of every
problem in NP (i.e. every coNP problem) is also in P, i.e., P=NP=coNP.
(b) Not necessarily. NP=coNP simply means that for each problem in NP=coNP, both YES and NO answers can be verified in polynomial time. This does not trivially imply that these problems can also be solved in polynomial time.
(c) Given a graph k, we can solve k-Colour for each k ∈ {1,…,n}. (By Q2 part (a), we know that n is sufficient.) The smallest k for which G is k-colourable is then the answer of MinColour.
(d) Given a graph G and an integer k, we can solve MinColour to obtain k∗, and then check if k∗ k.
page 3 of 3 over…