# HG changeset patch
# User Eugen Sawin <sawine@me73.com>
# Date 1336569221 -7200
# Node ID 77de69aef70ec62268d9dbe4a625795b2f136cd5
# Parent  536889e989c30c2a06fa5c93409ec1f504216aee
Final ex2 solution.

diff -r 536889e989c3 -r 77de69aef70e exercises/solutions/sol02.tex
--- a/exercises/solutions/sol02.tex	Wed May 09 04:07:59 2012 +0200
+++ b/exercises/solutions/sol02.tex	Wed May 09 15:13:41 2012 +0200
@@ -57,10 +57,14 @@
   \item $E_2 = \{\{v_i,v_j\} \mid \{v_i,v_j\} \notin E\}$
   \item $k_2 = |V| - k$
 \end{itemize}
+If there is a vertex cover $V_2'$ of size $\leq k_2$, i.e. $\forall{e \in E}: \exists{v \in V_2'}: v \in e$ then it follows that there must be a clique of at least size $|V|-k_2$ in the complementary graph and vice versa, because for each disconnected vertex pair in one graph, there is a connected pair in the other.\\
+The construction takes linear time, hence it follows that $VertexCover \in NP$-$complete$. \qed\\\\
 (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.\\
 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:
 \begin{itemize}
   \item $V_2 = V \cup \{v_e \mid e \in E\}$
   \item $E_2 = E \cup \{\{v,v_e\} \mid v,v_e \in V_2$ and $e \in E\}$
 \end{itemize}
+By introducing the additional nodes for all vertices in $G$, we make sure that the dominating set $V_2'$, by covering all vertices in $G_2$, implicitely covers all edges in $G$. The other direction follows analogously, if a vertex cover $V'$ covers all edges in $G$ it follows that the same set covers all vertices in $G_2$.\\
+The construction takes linear time, hence it follows that $DominatingSet \in NP$-$complete$. \qed
 \end{document}