sawine@5: \documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
sawine@5: \usepackage{graphicx}
sawine@5: %\usepackage[latin1]{inputenc}
sawine@5: \usepackage{amsmath, amsthm, amssymb}
sawine@5: \usepackage{typearea}
sawine@5: \usepackage{algorithm}
sawine@5: \usepackage{algorithmic}
sawine@5: \usepackage{fullpage}
sawine@5: \usepackage{mathtools}
sawine@5: \usepackage[all]{xy}
sawine@5: \addtolength{\voffset}{-40pt}
sawine@5: \title{CSP Exercise 02 Solution}
sawine@5: \author{Eugen Sawin}
sawine@5: \renewcommand{\familydefault}{\sfdefault}
sawine@5: \newcommand{\E}{\mathcal{E}}
sawine@5: \newcommand{\R}{\mathcal{R}}
sawine@5: 
sawine@5: %\include{pythonlisting}
sawine@5: 
sawine@5: \pagestyle{empty}
sawine@5: \begin{document}
sawine@5: \maketitle
sawine@5: 
sawine@5: \section*{Exercise 2.1}
sawine@5: (a) The strongly connected components are the subgraphs induced by following sets of vertices.
sawine@5: \begin{itemize}
sawine@5:   \item $V_1 = \{v_1,v_2,v_5,v_6\}$
sawine@5:   \item $V_2 = \{v_3,v_4\}$
sawine@5: \end{itemize}
sawine@5: (b) The cliques are the the complete subgraphs induced by the following sets of vertices.
sawine@5: \begin{itemize}
sawine@5:   \item $V_1 = \{v_1,v_2,v_5\}$
sawine@5:   \item $V_{2-8} \in E$
sawine@5:   \item $V_{9-14} \in \{\{v_i\} \mid v_i \in V\}$
sawine@5: \end{itemize}
sawine@5: 
sawine@5: \section*{Exercise 2.2}
sawine@6: 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.
sawine@5: \begin{enumerate}
sawine@5:   \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$.
sawine@5:   \item If $F = W$ terminate, we have found a solution.\\
sawine@5:   Otherwise select any $w_i \notin F$ and add it to $B_1$ and $F$, i.e. $B_1 = B_1 \cup \{w_i\}$ and $F = F \cup \{w_i\}$.\\
sawine@5:   Add all its disliked neighbours to $B_2$, i.e. $B_2 = B_2 \cup \{w_j \mid \{w_i,w_j\} \in E\}$.\\
sawine@5:   If $B_1 \cap B_2 \neq \emptyset$ terminate, there was a conflict and therefore no possible solution.
sawine@5:   \item If there a $w_i \notin F$ with $w_i \in B_1 \cup B_2$ select it, otherwise continue with $2.$\\
sawine@5:   Add all its disliked neighbours to the other building, i.e. $w_i \in B_1 \implies B_2 = B_2 \cup \{w_j \mid (w_i,w_j) \in E\}$, $w_i \in B_2 \implies B_1 = B_1 \cup \{w_j \mid (w_i,w_j) \in E\}$ and $F = F \cup \{w_i\}$.\\
sawine@5:   If $B_1 \cap B_2 \neq \emptyset$ terminate, there was a conflict and therefore no possible solution.\\
sawine@5:   Otherwise continue with $3.$
sawine@5: \end{enumerate}
sawine@6: 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).
sawine@6: 
sawine@6: \section*{Exercise 2.3}
sawine@6: (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.\\
sawine@6: 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:
sawine@6: \begin{itemize}
sawine@6:   \item $V_2 = V$
sawine@6:   \item $E_2 = \{\{v_i,v_j\} \mid \{v_i,v_j\} \notin E\}$
sawine@6:   \item $k_2 = |V| - k$
sawine@6: \end{itemize}
sawine@7: 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.\\
sawine@7: The construction takes linear time, hence it follows that $VertexCover \in NP$-$complete$. \qed\\\\
sawine@6: (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.\\
sawine@6: 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:
sawine@6: \begin{itemize}
sawine@6:   \item $V_2 = V \cup \{v_e \mid e \in E\}$
sawine@6:   \item $E_2 = E \cup \{\{v,v_e\} \mid v,v_e \in V_2$ and $e \in E\}$
sawine@6: \end{itemize}
sawine@7: 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$.\\
sawine@7: The construction takes linear time, hence it follows that $DominatingSet \in NP$-$complete$. \qed
sawine@5: \end{document}