Fall 2012 Final
You can find the exam here. Instructor-provided solutions have not been made available, so these student-created solutions will have to suffice.
1Question 1¶
Consider a flow network ($G, s, t, {c_e}$).
(a) Prove or Disprove: There always exists a minimum cut which contains the edge with smallest capacity.
Disprove. Counterexample:
The minimum cut is the edge with a capacity of 5.
(b) Prove or Disprove: For every flow network with at most $m$ edges, there always exists a sequence of at most $m$ augmentations that leads to a maximum flow?
Using Ford-Fulkerson, choose an augmenting path from $s$ to $t$.
Push the bottleneck capacity of the path to each edge.
At each iteration, at least one edge will reach its maximum flow value.
Thus, after at most $m$ iterations, all $m$ edges will have reached their optimal values and we will have reached the maximum flow.
1.1Accuracy and discussion¶
(a) Accurate and discussed.
(b) Question 2 on assignment 1. See the solutions.
2Question 2¶
Write the dual of the following linear program:
(omitted, see the exam)
Min: $$8y_1 + 4y_2$$
s.t.: $$\begin{align}
y_1+y_2 &\geq 1\\
y_1+2y_2&\geq 1\\
y_1 &\geq 4\\
y_1,y_2 &\geq 0
\end{align}$$
2.1Accuracy and discussion¶
very unsure - @hc6
I got the same thing - @dellsystem
3Question 3¶
State the strong duality theorem for linear programs.
For a maximisation problem: any feasible solution of primal $\leq$ optimal solution of primal = optimal solution of dual $\leq$ feasible solution of dual.
(Change it to $\geq$ for minimisation problems.)
To be more precise, the strong duality theorem states that if either the primal or the corresponding dual has a finite optimal value, then so does the other; what's more, these values are equal.
3.1Accuracy and discussion¶
10 marks for this??? wtf - @hc6
I don't recall the exact definition he used in class, and I can't find it in the notes. See these random notes to see what someone else says about the issue.
4Question 4¶
Show that the following problem belongs to P:
$$ X = \{\langle G \rangle : \text{G has an independent set of size } n - 10\} $$(Here $n$ is the number of vertices of $G$, and an independent set is a set of vertices, no two of which are adjacent).
There are a total of $\displaystyle \binom{n}{n-10}$ ways of picking $n-10$ vertices from a set of $n$, which is $O(n^{10})$. Checking if a set is independent takes $O(n)$ time, so the algorithm will be $O(n^{11})$ and thus will run in polynomial time.
4.1Accuracy and discussion¶
Looks legit. Pretty similar to question 4 on the sample final, and the answer provided for that follows the same idea. - @dellsystem
5Question 5¶
Write a linear program for solving the following problem: Given an $n \times n$ matrix $A$ and an $n$-dimensional vector $b$, we want to find a vector $x$ such that $Ax = b$ and that $(\min^n_{i=1} x_i)$ is maximized.
We add an extra variable $x_{n+1}$. Then we formulate the linear program as follows:
$$ \begin{align} \text{Max: }&x_{n+1}\\ \text{s.t.: }x_{n+1} &\leq x_i \tag{For all x}\\ Ax &= b \end{align} $$
5.1Accuracy and discussion¶
should be correct - @hc6
6Question 6¶
Show that the following problem is NP-complete:
$$X = \{\langle G \rangle: G\text{ has a cycle length of at least } n-1\}$$
It is in NP: a cycle of n-1 vertices is an example of a YES instance of the certificate.
If $n$ is the number of vertices in $G$, we can poly reduce Hamiltonian cycle to this by adding a terminal or disconnected vertex to any vertex in $G$, then run this algorithm on the new $G'$. If yes, then $G$ has a Hamiltonian cycle
6.1Accuracy and discussion¶
ok - @dellsystem
7Question 7¶
Show that the following problem is NP-complete:
Input: An integer and a graph $G = (V,E)$ where every vertex $v$ has a cost $c_v \geq$ 0
Question: Does $G$ have an independent set whose total cost is exactly $m$?
Proof that it's in NP: a certificate consists of a possible independent set and a cost $m$. To check a certificate, we add up the cost of the set, and see if it equals $m$. Yes if it is, No if it is not. This can be done in polynomial time.
Proof that it's NP-hard: We reduce maximum independent set to this. For any graph $G$ with $n$ vertices we set the cost of each vertex to 1, and call this algorithm with $G$ and $n$. If it fails we call it with $G$, $n-1$, and so on, until we get to 0. This will take a maximum of $n$ iterations, so this reduction can be done in polynomial time. Whenever it succeeds, the $m$ of that iteration will be size of the maximum independent set.
7.1Accuracy and discussion¶
Proof given by @hc6. I cleaned up the explanation (and grammar) a bit but didn't really read it, to be honest - @dellsystem
Okay I read it. Looks good. - @dellsystem
8Question 8¶
Consider the MAX-CUT problem: Given a graph $G$, we want to partition its vertices into two sets $A$ and $B$ such that the number of edges between $A$ and $B$ is maximized. Show that the following is a $\frac{1}{2}$ factor approximation algorithm for MAX-CUT
- Let $v_1, \ldots, v_n$ be the vertices of $G$.
- Set $A:=\{\}$ and $B:=\{\}$.
- For $i = 1, \ldots, n$:
- if $v_i$ has more neighbors in A than in B, add it to B, otherwise add it to A
Consider an arbitrary edge $e$ in the graph. Now, $e$ has two vertices, $v_i$ and $v_j$; let $v_i$ be the vertex that comes first in the ordering (so $i < j$). We'll refer to this vertex being responsible for edge $e$. We will then denote the number of edges that $v_i$ is responsible for by $r_i$. Note that since there is exactly one vertex responsible for every edge, $\sum r_i = $ the number of edges in the graph, which we'll call $m$.
Now let's consider what happens when we're deciding where to place $v_i$. The algorithm ensures that if $v_i$ has more neighbours in - and thus more edges connected to - $A$, then we place it in $B$, and vice-versa. Then, all those edges connected to $A$ (or $B$) will become part of the $A$-$B$ cut. Clearly, this will constitute at least $\frac{1}{2}r_i$ edges; otherwise, there would be more edges connected to the set that we've placed $v_i$ in, in which case the algorithm would place $v_i$ in the other set.
The number of edges in the cut upon the termination of the algorithm is then given by the sum of the number of edges added by each responsible vertex. If we call this APPROX, we have: APPROX $\geq \sum \frac{1}{2} r_i = \frac{1}{2} \sum r_i = \frac{m}{2}$. Since $m$ is the upper bound for the optimal solution (as the cut cannot contain more edges than there are in the graph), we have that $m \geq $ OPT and so APPROX $\geq \frac{m}{2} \geq$ OPT/2, which tells us that this is a $\frac{1}{2}$-factor algorithm. $\blacksquare$
8.1Accuracy and discussion¶
Proof taken from this random PostScript file.
9Question 9¶
Formulate the maximum independent set problem as an Integer Linear Program. (In the maximum independent set problem, given a graph $G = (V, E)$, we want to find the largest set $S$ of vertices in $G$ such that no two vertices in $S$ are adjacent.)
We assign $x_i$ to each vertex.
Max:
$$\begin{align} \sum_{i \in V} x_i\\ \text{such that} \quad x_u + x_v \leq 1\tag{For each edge $uv \in E$} \\ x_i \in \{1,0\} \tag{For each vertex $i \in V$} \end{align}$$
9.1Accuracy and discussion¶
Proof by @hc6. I'll read it later - @dellsystem
Read. Looks good - @dellsystem
10Question 10¶
Let G be the complete graph on $n$ vertices. We want to color the edges of $G$ with two colors Red and Blue such that the number of monochromatic triangles (i.e. triangles which are colored all red or all blue) is minimized. If we color the edge at random, then what is the expected number of monochromatic triangles?
There are $\binom{n}{3}$ triangles in a complete graph with $n$ vertices, and each triangle has a $\frac{1}{4}$ chance of being monochromatic ($\frac{1}{2}^3$ chance of being all blue, $\frac{1}{2}^3$ of being all red, so $\frac{1}{4}$ total). The linearity of expectation tells us that the total expected number of monochromatic triangles will be $\frac{1}{4}\binom{n}{3}$.
10.1Accuracy and discussion¶
Should be correct! Verified by bruteforce program https://gist.github.com/4248610 - @hc6
k - @dellsystem