### Midterm 2.1 NP Completeness

A. Give forward-instance construction from Subset-Sum instance $y$ $(w, W)$ into 2-D shortest path instance $x^y$ $(V, E, s, t, c_1, c_2, \theta_1, \theta_2)$.

1. Set $V$ = ($s \cup t \cup w_i$)
2. Set $E = (\emptyset)$:
* create edge $(s, w_i)$ with $c_1(s, w_i) = w_i$ and $c_2(s, w_i) = 0$
* create edge $(w_i, t)$ with $c_1(w_i, t) = 0$ and $c_2(w_i, t) = w_i$
3. $\theta_1 = s_1 \in S$
4. $\theta_2 = s_2 \in S$

B. Create V: $O(1)$, Create E: $O(n^2)4, where $n = |w|$. Create $\theta_1$, $\theta_2$: $O(1$
Runtime: $O(n^2)$

C. 

D. 

E. $S_1 = 3$, $S_2 = 4$
It follows that $\theta_1$ would be set to $3$ and $\theta_2$ would be set to $4$.

F. For solution certificate paths (s, 3, t) for $\theta_1$, $S_1 = 3$ and (s, 4, t) for $\theta_2$, $S_2 = 4$.

### Question 2
A. Yes instance of S of indep-set to $S^y$ for well-sep
1. For each $s_i \in S$, add vertex corresponding to $s_i$ to $S^y$

B. Prove that forward certificate construction is correct:
#### Claim 1: The cardinality of $S$ and $S^y$ are equal
Trivial proof, since we add each element of $S$ to $S^y$, we create sets of same size

#### Claim 2: There are no two-hop paths or edges between elements of $S^y$:
1. Let us first prove that there are no edges between elements of $S^y$ by using contradiction:
* Assume that there is an edge between elements of $S^y$. Then it follows that one of these vertices must have corresponded to an edge in the original graph in the indep-set problem G(V, E).
* This is a contradiction, because we cannot set the certificate for $S$ to include edges, since a proper construction of a certificate for the indep-set problem has only vertices, therefore, it cannot be the case that any elements in $S^y$ share an edge

2. Let us now prove that there is no two-hop path between elements of $S^y$
* By definition of the forward instance construction, vertices selected correspond to vertices in the indep-set problem, so for there to exist a two-hop path between any elements in $S^y$, then it must be the case that the vertices in the $S$ certificate were not independent. (Because existence of two-hop path implies an existence of an intermediary edge between the two vertices in the indep-set graph).
* This cannot be the case for any proper solution certificate $S$ for the indep-set problem, so we prove claim 2.

C. Show that forward instance construction is inccorect.
Consider the following graph:

* Specifically, V = (1, 2, 3)
* E = $(1,2) \cup (2,3) \cup (3,1)$
* Then a yes certificate for the well-sep problem would be $S^y = (1,4)$; however, there would be no valid yes certificate for the indep-set problem, because there does not exist a subset of vertices in the indep-set graph with cardinality 2.

D. Simple fix: Stipulate that only vertices corresponding to vertices in the indep-set problem may be selected

E. Now, in this problem we can only select (1, 2, 3), which refer to vertices in the i-set problem. In this way, we cannot create any pair of two in this set that are well-separated; likewise, we cannot select more than one vertex to correspond to a valid solution certificate in the indep-set problem.