sawine@9: \documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
sawine@9: \usepackage{graphicx}
sawine@9: %\usepackage[latin1]{inputenc}
sawine@9: \usepackage{amsmath, amsthm, amssymb}
sawine@9: \usepackage{typearea}
sawine@9: \usepackage{algorithm}
sawine@9: \usepackage{algorithmic}
sawine@9: \usepackage{fullpage}
sawine@9: \usepackage{mathtools}
sawine@9: \usepackage[all]{xy}
sawine@9: \usepackage{tikz}
sawine@9: \usepackage{tikz-qtree}
sawine@9: \usetikzlibrary{decorations.pathmorphing} % noisy shapes
sawine@9: \usetikzlibrary{fit}					% fitting shapes to coordinates
sawine@9: \usetikzlibrary{backgrounds}	% drawin
sawine@9: \usetikzlibrary{shapes,snakes}
sawine@9: \addtolength{\voffset}{-20pt}
sawine@9: \title{CSP Exercise 03 Solution}
sawine@9: \author{Eugen Sawin}
sawine@9: \renewcommand{\familydefault}{\sfdefault}
sawine@9: \newcommand{\E}{\mathcal{E}}
sawine@9: \newcommand{\R}{\mathcal{R}}
sawine@9: 
sawine@9: %\include{pythonlisting}
sawine@9: 
sawine@9: \pagestyle{empty}
sawine@9: \begin{document}
sawine@9: \maketitle
sawine@9: 
sawine@9: \section*{Exercise 3.1}
sawine@9: The minimal network is $N_0 = \langle (v_1,v_2,v_3),(\{2,3\},\{1,2,3,4\},\{1,3,4\}),\{<_{(v_1,v_2)},<_{(v_1,v_3)},=_{(v_2,v_3)}\} \rangle$.
sawine@9: 
sawine@9: \section*{Exercise 3.2}
sawine@9: (a) The network for the puzzle is \emph{(we do not name the variables consecutively to keep a clear connection to the original puzzle fields)}
sawine@9: \begin{align*}
sawine@9: N = \langle (v_1,v_2,v_3,v_8),(\{ATOLL\},\{TOLL,HEAT\},\{EAT\},\{TOLL,HEAT\}),\{R_{v_1,v_2,v_8},R_{v_2,v_3},R_{v_3,v_8}\} \rangle
sawine@9: \end{align*}
sawine@9: with
sawine@9: \begin{align*}
sawine@9: R_{v_1,v_2,v_8} &= \{(ATOLL,HEAT,TOLL)\}\\
sawine@9: R_{v_2,v_3} &= \{(HEAT,EAT)\}\\
sawine@9: R_{v_3,v_8} &= \{(EAT,TOLL)\}
sawine@9: \end{align*}
sawine@9: (b) See figure 1.
sawine@9: \begin{figure}[h]
sawine@9: \centering
sawine@9: \tikzstyle{var}=[circle,
sawine@9:   draw=black!100,
sawine@9:   fill=black!0]
sawine@9: \begin{tikzpicture}[>=latex,text height=1.5ex,text depth=0.25ex]
sawine@9:   \matrix[row sep=0.2cm,column sep=0.5cm] {    
sawine@9:     & \node(v1)[var]{$v_1$}; & &\\
sawine@9:     \node(v2)[var]{$v_2$}; & \node(v3)[var]{$v_3$}; & \node(v8)[var]{$v_8$};\\
sawine@9:   };
sawine@9:   \path[-]
sawine@9:   (v1) edge (v2)
sawine@9:   (v1) edge (v8)
sawine@9:   (v2) edge (v3)
sawine@9:   (v3) edge (v8)
sawine@9:   ;      
sawine@9: \end{tikzpicture}
sawine@9: \caption{(3.2b) primal constraint graph of $N$}
sawine@9: \end{figure}\\
sawine@9: (c) See figure 2.
sawine@9: \begin{figure}[h]
sawine@9: \centering
sawine@9: \tikzstyle{var}=[ellipse,
sawine@9:   draw=black!100,
sawine@9:   fill=black!0]
sawine@9: \begin{tikzpicture}[>=latex,text height=1.5ex,text depth=0.25ex]
sawine@9:   \matrix[row sep=0.2cm,column sep=0.5cm] {    
sawine@9:     & \node(v1v2v8)[var]{$v_1,v_2,v_8$};\\
sawine@9:     \node(v2v3)[var]{$v_2,v_3$}; & &\node(v3v8)[var]{$v_3,v_8$};\\
sawine@9:   };
sawine@9:   \path[-]
sawine@9:   (v1v2v8) edge node[auto=right]{$v_2$} (v2v3)
sawine@9:   (v1v2v8) edge node[auto=left]{$v_8$} (v3v8)
sawine@9:   (v2v3) edge node[auto=left]{$v_3$} (v3v8)
sawine@9:   ;      
sawine@9: \end{tikzpicture}
sawine@9: \caption{(3.2c) dual constraint graph of $N$}
sawine@9: \end{figure}
sawine@9: 
sawine@10: \section*{Exercise 3.3}
sawine@11: There are more trivial examples with the required properties and it would be easier to prove the properties on them in a formal way. However, we tried to find an example, which works for all three parts of this exercise with minimal modifications. We traded off formal proofs for intuitive understanding of the underlying differences between these relations.\\\\
sawine@10: (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)\}$.
sawine@9: 
sawine@10: 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)\}$.
sawine@10: 
sawine@11: 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 $R'$ it follows that all solutions of the projection network are also in the relation, i.e., $Sol(Proj(R_S)) = R_S$.
sawine@10: 
sawine@10: 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).
sawine@10: 
sawine@12: 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 projection 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).
sawine@10: 
sawine@10: Given that the relation $R_S$ itself and all its possible projections have binary representations, it holds that $R_S$ is binary decomposable. \qed\\\\
sawine@10: (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\}$.
sawine@10: 
sawine@11: 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 \subseteq Sol(Proj(R_S))$ and $R_S \neq Sol(Proj(R_S))$.
sawine@10: 
sawine@10: 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\\\\
sawine@10: (b) This time we modify the relation like this
sawine@10: \[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\}\]
sawine@10: with domains $D_i=\{0,1,2\}$ again.
sawine@10: 
sawine@10: 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$).
sawine@10: 
sawine@11: 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\\\\
sawine@9: \end{document}