Advanced Algorithms Quiz 1: 29 October 2023 (September 2023 term)

Which of the following statements is true?

Statement 1: For every graph $G$ and every maximum flow on $G$, there always exists an edge such that increasing the capacity on that edge will increase the maximum flow that's possible in the graph.

Statement 2: Suppose the maximum $(s,t)$-flow of some graph has value $f$. Now we increase the capacity of every edge by 1. Then the maximum $(s,t)$-flow in this modified graph will have value at most $f + 1$.

Consider the following instance of the stable matching problem for 4 men (PQRS) and 4 women (WXYZ).

P: W > X > Y > Z
Q: X > Y > Z > W
R: W > X > Z > Y
S: X > Y > W > Z

and

W: S > Q > R > P
X: P > S > Q > R
Y: R > P > Q > S
Z: R > P > S > Q

Consider the following matching: M = {(P, W), (Q, X), (R, Z), (S, Y)}.

Which of the following is a blocking pair in the matching above?

Consider 4 sets as follows: $W = \{w_1, w_2, w_3\}$, $X = \{x_1, x_2\}$, $Y = \{y_1, y_2, y_3\}$ and $Z = \{z_1, z_2\}$. Suppose we are also given capacity constraints are as follows:

$c(w_2) = c(y_1) = c(y_3) = 1,$

$c(w_1) = c(w_3) = c(x_2) = c(y_2) = c(z_1) = 2,$

$c(x_1) = c(z_2) = 3$

$c(w_i, x_j) = 1, \text{ for all } w_i \in W \text{ and all } x_j \in X,$

$c(y_i, z_j) = 1, \text{ for all } y_i \in Y \text{ and all } z_j \in Z$

$c(x_1, y_1) = 1, c(x_1, y_2) = 2, c(x_1, y_3) = 1$

$c(x_2, y_1) = 0, c(x_2, y_2) = 2, c(x_2, y_3) = 1.$

Identify the size of a largest collection of 4-tuples from the sets $W, X, Y$ and $Z$ satisfying the given constraints.