\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}

\usepackage{graphicx}

%\usepackage[latin1]{inputenc}

\usepackage{amsmath, amsthm, amssymb}

\usepackage{typearea}

\usepackage{algorithm}

\usepackage{algorithmic}

\usepackage{fullpage}

\usepackage{mathtools}

\usepackage[all]{xy}

\usepackage{tikz}

\usepackage{tikz-qtree}

\usetikzlibrary{decorations.pathmorphing} % noisy shapes

\usetikzlibrary{fit}					% fitting shapes to coordinates

\usetikzlibrary{backgrounds}	% drawin

\usetikzlibrary{shapes,snakes}

\addtolength{\voffset}{-20pt}

\title{CSP Exercise 05 Solution}

\author{Eugen Sawin}

\renewcommand{\familydefault}{\sfdefault}

\newcommand{\R}{\mathcal{R}}

\newcommand{\N}{\mathbb{N}}

\newcommand{\C}{\mathcal{C}}

\newcommand{\bo}{\mathcal{O}}

%\include{pythonlisting}

\pagestyle{empty}

\begin{document}

\maketitle

%

\section*{Exercise 5.1}

(a) The following table shows the states during the AC3 iterations.\\\\

\begin{tabular}{r l l l}

Iteration & Queue & Revise & Domains\\\hline\\

      $0$ & $\{(v_1,v_2),(v_2,v_1),

               (v_2,v_3),(v_3,v_2),

               (v_1,v_3),(v_3,v_1)\}$

          & $$ 

          & $(\{1,2,3,4,5\},

              \{1,2,3,4,5\},

              \{1,2,3,4,5\})$\\

      $1$ & $\{(v_1,v_2),(v_2,v_1),

               (v_2,v_3),(v_3,v_2),

               (v_1,v_3)\}$

          & $(v_3,v_1)$

          & $(\{1,2,3,4,5\},

              \{1,2,3,4,5\},

              \{1,2,3,4,5\})$\\

      $2$ & $\{(v_1,v_2),(v_2,v_1),

               (v_2,v_3),(v_3,v_2)

               \}$

          & $(v_1,v_3)$

          & $(\{1,2,3,4,5\},

              \{1,2,3,4,5\},

              \{1,2,3,4,5\})$\\

      $3$ & $\{(v_1,v_2),(v_2,v_1),

            (v_2,v_3)\}\cup\{(v_1,v_3)\}$

          & $(v_3,v_2)$

          & $(\{1,2,3,4,5\},

              \{1,2,3,4,5\},

              \{1,2\})$\\

      $4$ & $\{(v_1,v_2),(v_2,v_1),

            (v_2,v_3)\}\cup\{\}$

          & $(v_1,v_3)$

          & $(\{1,2\},

              \{1,2,3,4,5\},

              \{1,2\})$\\

      $5$ & $\{(v_1,v_2),(v_2,v_1)\}$

          & $(v_2,v_3)$

          & $(\{1,2\},

              \{1,2\},

              \{1,2\})$\\

      $6$ & $\{(v_1,v_2)\}$

          & $(v_2,v_1)$

          & $(\{1,2\},

              \{1,2\},

              \{1,2\})$\\

      $7$ & $\{\}$

          & $(v_1,v_2)$

          & $(\{1,2\},

              \{1,2\},

              \{1,2\})$\\

\end{tabular}\\\\\\

(b) The following table shows the states during the PC2 iterations.\\\\

\begin{tabular}{r l l l l l}

  Iteration & Queue & Revise-3 & $R_{v_1,v_2}$ & $R_{v_2,v_3}$ & $R_{v_1,v_3}$\\

  \hline\\

      $0$ & $\{(1,3,2),(1,2,3),(2,1,3)\}$

          & $ $ 

          & $\{(1,2),(2,1)\}$

          & $\{(1,1),(1,2),(2,1)\}$

          & $\{(1,1),(1,2),(1,3),$\\

      &&&&& $(1,4),(1,5),(2,2),$\\

      &&&&& $(2,3),(2,4),(2,5),$\\

      &&&&& $(3,3),(3,4),(3,5),$\\

      &&&&& $(4,4),(4,5),(5,5)\}$\\

      $1$ & $\{(1,3,2),(1,2,3)\}$

          & $(\{v_2,v_1\},v_3)$ 

          & $\{(1,2),(2,1)\}$

          & $\{(1,1),(1,2),(2,1)\}$

          & $\{(1,1),(1,2),(1,3),$\\

      &&&&& $(1,4),(1,5),(2,2),$\\

      &&&&& $(2,3),(2,4),(2,5),$\\

      &&&&& $(3,3),(3,4),(3,5),$\\

      &&&&& $(4,4),(4,5),(5,5)\}$\\

      $2$ & $\{(1,3,2)\}$

          & $(\{v_1,v_2\},v_3)$ 

          & $\{(1,2),(2,1)\}$

          & $\{(1,1),(1,2),(2,1)\}$

          & $\{(1,1),(1,2),(1,3),$\\

      &&&&& $(1,4),(1,5),(2,2),$\\

      &&&&& $(2,3),(2,4),(2,5),$\\

      &&&&& $(3,3),(3,4),(3,5),$\\

      &&&&& $(4,4),(4,5),(5,5)\}$\\

  $3$ & $\{\}\cup\{(2,1,3),(2,3,1)\}$

          & $(\{v_1,v_3\},v_2)$ 

          & $\{(1,2),(2,1)\}$

          & $\{(1,1),(1,2),(2,1)\}$

          & $\{(1,1),(2,2)\}$\\

  $4$ & $\{(2,1,3)\}\cup\{(1,2,3),(1,3,2)\}$

          & $(\{v_2,v_3\},v_1)$ 

          & $\{(1,2),(2,1)\}$

          & $\{(1,2),(2,1)\}$

          & $\{(1,1),(2,2)\}$\\

  $5$ & $\{(2,1,3),(1,2,3)\}$

          & $(\{v_1,v_3\},v_2)$ 

          & $\{(1,2),(2,1)\}$

          & $\{(1,2),(2,1)\}$

          & $\{(1,1),(2,2)\}$\\

  $6$ & $\{(2,1,3)\}$

          & $(\{v_1,v_2\},v_3)$ 

          & $\{(1,2),(2,1)\}$

          & $\{(1,2),(2,1)\}$

          & $\{(1,1),(2,2)\}$\\

  $7$ & $\{\}$

          & $(\{v_2,v_1\},v_3)$ 

          & $\{(1,2),(2,1)\}$

          & $\{(1,2),(2,1)\}$

          & $\{(1,1),(2,2)\}$

\end{tabular}

\section*{Exercise 5.3}

(a) In a path-consistent network for every pair $(a_i,a_j)\in R_{ij}$, there exists an $a_k\in D_k$, such that $(a_i,a_k)\in R_{ik}$ and $(a_k,a_j)\in R_{kj}$.

Since all the $R_{ij}$ are non-empty and all our variables $v_i$ share the same domain values, it follows that all $v_i$ are arc-consistent relative to $v_k$ and all $v_k$ are arc-consistent relative to $v_j$, which induces that all $R_{ij}$ are arc-consistent, since otherwise they would be no $a_i\in D_i$, such that $(a_k,a_i)\in R_{ki}$ and $(a_i,a_j)\in R_{ij}$. \qed\\\\

(b) We know that all sets $A_m\subseteq\{0,1\}$ are non-empty, i.e., $1\leq|A_m|\leq2$ for all $1\leq m\leq l$. Therefore it holds that the intersection of two sets $A_q=A_o\cap A_p$ has cardinality $0\leq|A_q|\leq \min\{|A_o|,|A_p|\}\leq 2$.

WLOG, we know that $A_q$ becomes the empty set, iff $A_o=\{0\}$ and $A_p=\{1\}$ and any combination of $A_o=\{0,1\}$ and $A_p\subset A_o$ yields the set $A_q=A_p$. Therefore it holds that for $\bigcap_{1\leq m\leq l}{A_m}=\emptyset$ to hold, there must be two sets holding the distinct elements $0$ and $1$ respectively, as has been shown. \qed\\\\

(c) We prove by contradiction. Assume that the partial assignment on $v_1,...,v_{k-1}$ can not be extended to $v_k$, i.e., $\bigcap_{2\leq i\leq k-1}{\{a_k\mid (a_i,a_k)\in R_{ik}\}}=\emptyset$. By (b) follows that there must be $2\leq i\neq j\leq k-1$, such that $\{a_k\mid(a_i,a_k)\in R_{ik}\}\cap\{a_k\mid(a_j,a_k)\in R_{jk}\}=\emptyset$.

WLOG let $\{a_k\mid(a_i,a_k)\in R_{ik}\}=\{0\}$ and $\{a_k\mid(a_j,a_k)\in R_{jk}\}=\{1\}$. We know that we have non-empty constraints on all variable pairs $R_{ij}$ and there is a consistent assignment $(a_i,a_j)\in R_{ij}$. By our assumption there is an assignement $(a_i,0)\in R_{ik}$ but no $(a_j,0)\in R_{jk}$. This contradicts to the definition of path-consistency, where for every pair $(a_i,a_j)\in R_{ij}$, there exists an $a_k\in D_k$, such that $(a_i,a_k)\in R_{ik}$ and $(a_k,a_j)\in R_{kj}$. Therefore there can not be such an assumption in a path-consistent network with given properties and we can extend the assignment to $v_k$. \qed

\end{document}