Fall 2011 Final

Student-provided solutions to the Fall 2011 final exam, possibly instructor-verified. You can view the original exam here.

It is recommended that you do this exam yourself before checking the solutions provided here. If you notice any errors with the content on this page, feel free to either contact @dellsystem or edit the page directly.

Under construction.

1Question 1¶

Let $(A, B)$ be a minimum cut in a flow network, and suppose that there are exactly two edges $e_1$ and $e_2$ going from $A$ to $B$.

(a) Prove: Decreasing the capacity of $e_1$ by 1 and at the same time increasing the capacity of $e_2$ by 1 cannot increase the value of the maximum flow.
(b) Disprove: Decreasing the capacity of $e_1$ by 1 and at the same time increasing the capacity of $e_2$ by 1 cannot decrease the value of the maximum flow.

(a) Suppose a flow of $f_1$ flows through $e_1$ and a flow of $f_2$ flows through $e_2$. The only case where the maximum flow would increase if the capacity of $e_1$ was decreased by 1 and the capacity of $e_2$ was increased by 1 would be if lowering $e_1$ by 1 alone doesn't decrease the maximum flow, and at the same time, increasing $e_2$ increases the maximum flow by 1. If decreasing the capacity of $e_1$ doesn't decrease the maximum flow, it means there are another set of edges in $A$ that would form a lower cut, making $(A, B)$ not the lowest cut.

(b) Increasing the capacity of $e_2$ could have no effect on the max flow (not sure how to express this, but if $e_2$ isn't the limiting edge, increasing it by 1 would have no effect). Decreasing the capacity of $e_1$ can decrease the maximum flow because if $e_1$ was a limiting edge, it means that all the capacity is used, and decreasing it would lower the maximum flow. In this case it would decrease the overall max flow by 1.

1.1Accuracy and discussion¶

Answers by @hc6. Good enough - @dellsystem

2Question 2¶

Write the dual of the following linear program: (omitted)

Max: $8y_1 + 4y_2$
Constraints: $y_1-y_2 = 0$
$y_1 + y_2 \leq 1$
$y_1 \geq 0$, $y_2$ is universal

2.1Accuracy and discussion¶

Well, I re-did this question thinking that @hc6 had written it up originally, and I got the same answer. That counts as a verification, right? Incidentally, the min/max should be 6 for the primal/dual respectively. - @dellsystem

3Question 3¶

If a maximization linear program is unbounded, then what can be said about its dual? (Is it unbounded, feasible and bounded, or infeasible?) Explain.

The dual is infeasible. By the weak duality theorem, we know that any solution to the primal (maximisation) is less than or equal to any solution for the dual. But if the primal is unbounded, then the dual must be infeasible, for there is no possible value for the dual that is greater than an arbitrarily large solution to the primal.

3.1Accuracy and discussion¶

Good enough - @dellsystem

4Question 4¶

Show that the following problem belongs to P:
$$\{X = \langle G \rangle: G \,\text{has an independent set of size 10} \}$$

Select all the different sets of size 10. For each one, check independence. If there are $n$ vertices, there are $\displaystyle \binom{n}{10}$ ways to choose sets of size 10, which takes $O(n^{10})$ iterations, checking if each set is an independent set takes $O(n)$, thus the algorithm is $O(n^{11})$

4.1Accuracy and discussion¶

Should be okay (the original was missing the $O(n)$ for the independent set checking, which was provided by @hc6) - @dellsystem

Shouldn't the cost for checking a solution be the size of $E$? I think the total cost should be $$O(|V|^{10}*|E|)$$
@gergi

5Question 5¶

Describe the complexity class PSPACE.

Algorithms that take a polynomial amount of space, encompasses all of NP and P

5.1Accuracy and discussion¶

Should be trivial - @dellsystem

6Question 6¶

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 $\max_{i=1}^n |x_i|$ is minimized (Hint: Try to use the constraints of the form $y \geq a$ and $y \geq -a$).

We add a new variable $x_{n+1}$, then we formulate the linear program as follows:

$$\begin{align} \text{minimize: }x_{n+1}\\ x_{n+1}&\geq x_i \tag{for all i}\\ x_{n+1}&\geq -x_i \tag{for all i}\\ Ax&=b\\ \text{x is universal} \end{align}$$

6.1Accuracy and discussion¶

By @hc6. Sure. - @dellsystem

7Question 7¶

Show that the following language is NP-complete:
$$X = \{\langle G, k \rangle : G \text{ has a cycle of length at least } k\}$$

Certifier: Given a cycle, check that its length is $k$, and that it really is a cycle. Can be done in polytime.

NP-hardness: Reduce Hamiltonian cycle to this, with $k$ being the size of the graph (number of vertices).

7.1Accuracy and discussion¶

Sounds okay. - @dellsystem

8Question 8¶

A kite is a graph on an even number of vertices, say $2k$, in which $k$ of the vertices form a clique and the remaining $k$ vertices are connected in a tail that consists of a path joined to one of the vertices of the clique. Prove that KITE is NP-complete, where
$$\text{KITE} = \{ \langle G, k \rangle : G \text{ has a subgraph which is a kite on } 2k \text{ vertices}\}$$

Proof of NP: given a graph on 2k vertices, look for a tail with length k, then for the remaining k vertices, check for complete connectedness.

Proof of NP-hardness: Reduce maximal clique to this. Suppose we want to find the maximal clique in a graph G with n vertices. For the first iteration we create a path with n vertices, then attach this path to every vertex in G, and check to see if it's a kite every time. If it outputs no, reduce the length of the tail by 1, and connect to every vertex again. Whenever it outputs yes, we know the maximal clique size will the the size of the tail of that iteration. It will take a total of $n^2$ iteration to check, thus maximal clique is polynomial reduced to KITE.

8.1Accuracy and discussion¶

i think i'm right... right? - @hc6

Looks fine - @dellsystem

9Question 9¶

Show that the following language is NP-complete: (omitted. Nope, added by @cdesmontagnes)

$$Z= \left \{ \left \langle \left \{ w_1, w_2, ..., w_n \right \} , k \right \rangle | w_1, w_2, ..., w_n \in \mathbb{N}^+ \ and \ k \in \mathbb{N}^+ . \exists S\subseteq \left \{ w_1, w_2, ..., w_n \right \} s.t. \ \sum_{w \in S} w = 2^k \right \}$$

Proof of NP: Produce the subset and the value of $k$ as a certificate. Check that the subset sums to $2^k$.

Proof of NP-hardness: Reduce subset sum to this. Add $\sum w_i + 2^k - 1$?

9.1Accuracy and discussion¶

TBA

10Question 10¶

(a) Suppose the optimal solution satisfies $m$ clauses, and $\theta_{\text{true}}$ satisfies $n$ clauses, $\theta_{\text{false}}$ would then satisfy $m-n$ clauses. $\max(n,m-n)$ is at least 1/2 as big as m.

(b) $(x_1 \lor x_2) \land (\neg x_1 \lor \neg x_2)$.

10.1Accuracy and discussion¶

a) I guess you need to prove that flipping all the true to false would satisfy an inverse number of clauses.. that seems pretty trivial though... all the clauses that are false have a false term inside every one of them, and reversing them would making all the terms true, and vice versa.

11Question 11¶

Make the ILP, then the LP relaxation, then round anything $\geq 1/3$ up to 1.

11.1Accuracy and discussion¶

what

12Question 12¶

Done in class

12.1Accuracy and discussion¶

TBA