CMSC 27200 — Problem Set 7

Instructions

This problem set is due on Wednesday May 27, 2020 at 20:00 Central, to be submitted on Gradescope. Each problem is worth 10 marks in total.

Problems

1. Let $G = (V,E,s,t,c)$ be a flow network and let $(S,T)$ be a minimum cut for $G$ with respect to the capacity function $c$. Consider the capacity function $c'$ defined by $c'(e) = c(e) + 1$ for all $e \in E$. Is $(S,T)$ a minimum cut for $G$ with respect to $c'$? Give either a proof showing that this is true or a counterexample showing that this is false.

2. As you are probably aware, courses offered by the Department of Computer Science are quite popular and it is often the case that there are more students trying to enroll in courses than there is space.

   Suppose that there are $n$ students and the department is offering $k$ courses for the upcoming quarter. Course $C_i$ has a strict enrollment limit of $\ell_{C_i}$. Each student $s_i$ can be enrolled in up to $c_{s_i}$ computer science courses. This number depends on things like which year the student is in or what the student's major/program is, but will range from 1 to 5 (lol). Each student may pre-register in as many courses as they are interested in but are not able to express preferences for courses. That is, a student is equally likely to be enrolled in any of the courses they expressed interest in.

   Describe and prove how to determine in polynomial time whether it is possible to enroll every student in the maximum number of CS courses they are allowed to.

3. Describe and prove how to solve the following problem in polynomial time: Given a flow network $G = (V,E,s,t,c)$ with capacity function $c$ defined by $c(e) = 1$ for all $e \in E$ and an integer $k \geq 0$, find a set $F \subseteq E$ of $k$ edges to remove such that the maximum flow in $G' = (V,E-F,s,t,c)$ is minimized across all possible choices of $F$.