1.1 --- a/exercises/solutions/sol03.tex Fri May 18 22:37:44 2012 +0200
1.2 +++ b/exercises/solutions/sol03.tex Sat May 19 04:25:58 2012 +0200
1.3 @@ -81,37 +81,28 @@
1.4 \caption{(3.2c) dual constraint graph of $N$}
1.5 \end{figure}
1.6
1.7 -\section*{Exercise 2.2}
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 - 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\}$.\\
1.13 - Add all its disliked neighbours to $B_2$, i.e. $B_2 = B_2 \cup \{w_j \mid \{w_i,w_j\} \in E\}$.\\
1.14 - If $B_1 \cap B_2 \neq \emptyset$ terminate, there was a conflict and therefore no possible solution.
1.15 - \item If there a $w_i \notin F$ with $w_i \in B_1 \cup B_2$ select it, otherwise continue with $2.$\\
1.16 - 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\}$.\\
1.17 - If $B_1 \cap B_2 \neq \emptyset$ terminate, there was a conflict and therefore no possible solution.\\
1.18 - Otherwise continue with $3.$
1.19 -\end{enumerate}
1.20 -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.21 +\section*{Exercise 3.3}
1.22 +(a) Let $R_S$ be the relation with $S=(x_1,...,x_n)$ for the constraint $x_1 > \sum_{i=2}^{n}x_i$ over the domains $D_i = \{0,1,2\}$, i.e., $R_S = \{(1,0,...,0)\} \cup \{(2,(x_i)_{1<i\leq n}) \mid \sum_{i=2}^{n}x_i < 2\}$ or more graphically $R_S = \{(1,0,...,0),$ $(2,0,...,0,1,0,...,0),(2,1,0,...,0), (2,0,...,0,1)\}$.
1.23
1.24 -\section*{Exercise 2.3}
1.25 -(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.26 -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.27 -\begin{itemize}
1.28 - \item $V_2 = V$
1.29 - \item $E_2 = \{\{v_i,v_j\} \mid \{v_i,v_j\} \notin E\}$
1.30 - \item $k_2 = |V| - k$
1.31 -\end{itemize}
1.32 -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.\\
1.33 -The construction takes linear time, hence it follows that $VertexCover \in NP$-$complete$. \qed\\\\
1.34 -(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.35 -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.36 -\begin{itemize}
1.37 - \item $V_2 = V \cup \{v_e \mid e \in E\}$
1.38 - \item $E_2 = E \cup \{\{v,v_e\} \mid v,v_e \in V_2$ and $e \in E\}$
1.39 -\end{itemize}
1.40 -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$.\\
1.41 -The construction takes linear time, hence it follows that $DominatingSet \in NP$-$complete$. \qed
1.42 +The projection network of $R_S$ is by definition $Proj(R_S) = \langle S, D_i = \pi_{x_i}(R_S), R_{x_i,x_j}' = \pi_{x_i,x_j}(R_S)\rangle$ with $R'_{x_1,x_j} = \{(1,0),(2,0),(2,1)\}$ and for $i \neq 1$ holds $R'_{x_i,x_j}=\{(0,0),(0,1),(1,0)\}$.
1.43 +
1.44 +The limited domains impose transitive relations $x_1 > x_i$ for all $1 < i \leq n$ and $x_i = x_j = 0 \lor x_i \neq x_j$ for $i \neq 1$. Since this imposed relations essentially reduce the contraint to the mentioned binary relations it follows that all solutions of the projection network are also in the relation, i.e., $Sol(Proj(R_S)) = R_S$.
1.45 +
1.46 +All projections of $R_S$ to a subset of $S$, so that $x_1$ is contained, basically reduces the network to the projection size, all properties remain unchanged, therefore the projection network of the projection of $R_S$ has only solutions which are in the projected relation (and vice versa).
1.47 +
1.48 +All projections of $R_S$ to a subset of $S$ without $x_1$ mean a reduction to the constraint $2 > \sum_{i=1}^{m}x_i$ where m is the projections size. This has obviously also a binary representation with $R'_{x_i,x_j} = \{(0,0),(1,0),(0,1)\}$. Again it follows that the projection network of this projection has only solutions which are in the projected relation (and vice versa).
1.49 +
1.50 +Given that the relation $R_S$ itself and all its possible projections have binary representations, it holds that $R_S$ is binary decomposable. \qed\\\\
1.51 +(c) We will do part (c) before (b) because here we use the same constraint as in part (a). However, we will expand the domains with $D_i = \{0,1,2,3\}$. This gives us the relation $R_S = \{(x_1,(x_i)_{1<i\leq n}) \mid \sum_{i=2}^{n}x_i < x_1\}$.
1.52 +
1.53 +This relation has no binary representation, because no set of binary relations can enforce the constraint for $x_1 = 3$. E.g. $(3,1,1,1,0,...,0)$ is a solution of $Proj(R_S)$, because it is consistent with the constraints $R'_{x_1,x_j}=\{(1,0),(2,0),(2,1),(3,0),(3,1),(3,2)\}$ and for $i\neq 1$ $R'_{x_i,x_j}=\{(0,0),(1,0),(0,1),(1,1),(2,0)\}$ while it is not contained in $R_S$. It follows that $R_S \neq Sol(Proj(R_S))$.
1.54 +
1.55 +We could have shown the same effect by leaving the domains untouched, but changing the constraint to $x_1 \geq \sum_{i=2}^nx_i$ instead, which has the same effect, it requires a systematic (here ternary) view over all variables. \qed\\\\
1.56 +(b) This time we modify the relation like this
1.57 +\[R_S=\{(x_1,(x_i)_{1<i\leq\frac{n-1}{2}},(x_j)_{\frac{n-1}{2}<j\leq n}) \mid \sum_{i=2}^{\frac{n-1}{2}}x_i < x_1 < \sum_{j=\frac{n-1}{2}+1}^{n}x_j\}\]
1.58 +with domains $D_i=\{0,1,2\}$ again.
1.59 +
1.60 +This modification does not change the property of the relation to have a binary representation, because solutions to the binary constraints are exactly the variable assignments from the relation (again due to the transitive relations over $x_1$).
1.61 +
1.62 +However, if we use a projection without $x_1$, we lose our pivot variable for the otherwise separted sets of variables. Solutions to such a projection network induced by the projected relation without $x_1$ will again lack the systematic view over the separated sets of variables and their sums, which yields possible solutions which are inconsistent with the projected relation. From this follows that our modified $R_S$ has a binary representation but is not binary decomposable. \qed
1.63 \end{document}