1.1 --- a/exercises/solutions/sol02.tex	Wed May 09 01:04:24 2012 +0200
     1.2 +++ b/exercises/solutions/sol02.tex	Wed May 09 04:07:59 2012 +0200
     1.3 @@ -35,7 +35,7 @@
     1.4  \end{itemize}
     1.5  
     1.6  \section*{Exercise 2.2}
     1.7 -We define the following undirected simple graph $G = \langle W, E \rangle$ with $\{w_i,w_j\} \in E$ iff $w_i$ and $w_j$ dislike each other. Additionally we define two sets $B_1 = B_2 = \{\}$ for the buildings and an auxiliary set $F = \{\}$ for remembering \emph{expanded} nodes.
     1.8 +We define the following undirected graph $G = \langle W, E \rangle$ with $\{w_i,w_j\} \in E$ iff $w_i$ and $w_j$ dislike each other. Additionally we define two sets $B_1 = B_2 = \{\}$ for the buildings and an auxiliary set $F = \{\}$ for remembering \emph{expanded} nodes.
     1.9  \begin{enumerate}
    1.10    \item For all $w_i \in W$ with $w_i \notin \bigcup E$ add $w_i$ to $B_1$ and $F$, i.e. $B_1 = B_1 \cup \{w_i\}$ and $F = F \cup \{w_i\}$. This way we assign all workers, who are liked by everyone to building $B_1$.
    1.11    \item If $F = W$ terminate, we have found a solution.\\
    1.12 @@ -47,5 +47,20 @@
    1.13    If $B_1 \cap B_2 \neq \emptyset$ terminate, there was a conflict and therefore no possible solution.\\
    1.14    Otherwise continue with $3.$
    1.15  \end{enumerate}
    1.16 -This is essentially a breadth-first search with random-walk used to jump to disconnected nodes. Assumming that set containment can be tested in $\mathcal{O}(1)$ and set intersection in $\mathcal{O}(n)$ we have an asymptotic complexity of $\mathcal{O}(|W| \cdot |E|)$.
    1.17 +This is essentially a random walk through the graph with some book keeping. Assumming that set containment can be tested in $\mathcal{O}(1)$ and set intersection in $\mathcal{O}(n)$ we have an asymptotic complexity of $\mathcal{O}(|W| \cdot |E|)$ (this includes the optimisation, that the intersection test is only done once when $F = W$ holds).
    1.18 +
    1.19 +\section*{Exercise 2.3}
    1.20 +(a) $VertexCover \in NP$ because by guessing the vertex set $V'$, we can iterate over all $\{v_1,v_2\} \in E$ and check if $v_1 \in V'$ or $v_2 \in V'$ holds in polynomial time.\\
    1.21 +We show $Clique \le_P VertexCover$. Given an undirected graph $G = \langle V,E \rangle$ and $k \in N$ we build a graph $G_2 = \langle V_2, E_2 \rangle$ so that there is a clique $V' \subseteq V$ with $|V'| \geq k$ iff there is a vertex cover $V_2' \subseteq V_2$ with $|V_2'| \leq k_2$ given following construction:
    1.22 +\begin{itemize}
    1.23 +  \item $V_2 = V$
    1.24 +  \item $E_2 = \{\{v_i,v_j\} \mid \{v_i,v_j\} \notin E\}$
    1.25 +  \item $k_2 = |V| - k$
    1.26 +\end{itemize}
    1.27 +(b) $Dominating Set \in NP$ because by guessing the vertex set $V'$, we can iterate over all $v \in V$ and check if $v \in V'$ or $\exists{v' \in V}: \{v,v'\} \in E$ holds in polynomial time.\\
    1.28 +We show $Vertex Cover \le_P DominatingSet$. Given an undirected graph $G = \langle V, E \rangle$ and $k \in N$ we build a graph $G_2 = \langle V_2, E_2 \rangle$ so that there is a vertex cover $V' \subseteq V$ with $|V'| \leq k$ iff there is a dominating set $V_2' \subseteq V_2$ with $|V_2| \leq k$ given following construction:
    1.29 +\begin{itemize}
    1.30 +  \item $V_2 = V \cup \{v_e \mid e \in E\}$
    1.31 +  \item $E_2 = E \cup \{\{v,v_e\} \mid v,v_e \in V_2$ and $e \in E\}$
    1.32 +\end{itemize}
    1.33  \end{document}