The Graph Isomorphism Problem

The graph isomorphism ($\mathsf{GI}$) problem is one of the few known problems in computational complexity that are in the complexity class $\mathsf{NP}$, but neither known to be in $\mathsf{P}$ nor in $\mathsf{NP}$-complete. So it is a very good candidate for a so called $\mathsf{NP}$-intermediate problem. Another well known candidate is factorization.
For many types of graphs the $\mathsf{GI}$ problem could be solved efficiently, i.e., using only poly($n$) many resources, whereof $n$ is the number of vertices in the graph. However, one is able to generate hard instances where all the algorithms fail and an exponential amount of resources is needed in order to solve the problem. But finding such hard instances is not easy. In particular for random graphs, the isomorphism problem is almost always easy. So the average complexity of $\mathsf{GI}$ is low, but the worst case complexity is hard.

Definition [Graph Isomorphism] Two graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$ are isomorphic if there is a bijective mapping $\sigma: V_1 \rightarrow V_2$ such that if there is an edge between the vertices $u$ and $v$ in $G$, i.e., $(u,v) \in E_1$, then there is an edge between the vertices $\sigma(u)$ and $\sigma(v)$ in $H$, i.e. $(\sigma(u),\sigma(v)) \in E_2$.

The actual description of the problem is easy and understandable even to people that perhaps see graphs first their first time. In Figure 1 the undirected graph $G$ is shown.

Figure 1 - The graph $G$

$G$ has $8$ vertices and each one is of degree $3$. In Figure 2 you can see the two graphs $H_1$ and $H_2$. One of these is isomorphic to $G$ and the other one is not.

Figure 2 - On the left it is graph $H_1$ and on the right $H_2$

Question: Suppose you could drag each vertex with your mouse. Which set of vertices can be rearranged such that the graph $G$ appears? That means, is $G \cong H_1$ or $G \cong H_2$?

Double Columnar Transposition (Part 1)

Even in the 21st century, there still exists cipher methods that can be executed by pencil and paper and that are concurrently strong enough to resists the computational power of modern PCs quite well. One of those cipher systems is the Double Columnar Transposition Cipher (DCTC), or for the german speaking readers Der Doppelwürfel.

[Double Columnar Transposition Cipher]. The DCTC works as follows: Assume a plaintext $\mathcal{P} = n_1 n_2 ... n_k$. Pick two key words from an (e.g.) english dictionary or even better two short sentences: $\mathcal{K}_1$ and $\mathcal{K}_2$ of length $s_1$ and $s_2$ respectively. To encrypt a message, write the plaintext in a block (or matrix) layout with $s_1$ columns. Now sort the columns regarding the first keyword $\mathcal{K}_1$. E.g. using the plaintext THIS IS IMPORTANT and the first keyword DOUBLE:

$$ \begin{bmatrix}
\textbf{D} & \textbf{O} & \textbf{U} & \textbf{B} & \textbf{L} & \textbf{E} \\
- & - & - & - & - & - \\
\text{T} & \text{H} & \text{I} & \text{S} & \text{I} & \text{S} \\
\text{I} & \text{M} & \text{P} & \text{O} & \text{R} & \text{T}\\
\text{A} & \text{N} & \text{T} & & & \\
\end{bmatrix} \stackrel{\text{sort}} {\rightarrow}
 \begin{bmatrix}
\textbf{B} & \textbf{D} & \textbf{E} & \textbf{L} & \textbf{O} & \textbf{U} \\
- & - & - & - & - & - \\
\text{S} & \text{T} & \text{S} & \text{I} & \text{H} & \text{I} \\
\text{O} & \text{I} & \text{T} & \text{R} & \text{M} & \text{P}\\
 & \text{A} & & & \text{N} & \text{T}\\
\end{bmatrix}  \stackrel{\text{read column by column}}{\rightarrow}$$
(The keyword above the text is only displayed for clarity reasons.) After sorting, read the text column by column from the block, thereby skipping the empty places in the last row. In this order write the text again in block-size form, this time with $s_2$ columns. Again, sort the block according to the second keyword $\mathcal{K}_2$, here CUBE:
 $$ \begin{bmatrix}
\textbf{C} & \textbf{U} & \textbf{B} & \textbf{E} \\
- & - & - & - \\
\text{S} & \text{O} & \text{T} & \text{I} \\
\text{A} & \text{S} & \text{T} & \text{I} \\
\text{R} & \text{H} & \text{M} & \text{N} \\
\text{I} & \text{P} & \text{T} &
\end{bmatrix} \stackrel{\text{sort}} {\rightarrow}
\begin{bmatrix}
\textbf{B} & \textbf{C} & \textbf{E} & \textbf{U} \\
- & - & - & - \\
\text{T} & \text{S} & \text{I} & \text{O} \\
\text{T} & \text{A} & \text{I} & \text{S} \\
\text{M} & \text{R} & \text{N} & \text{H} \\
\text{T} & \text{I} & & \text{P}
\end{bmatrix}\stackrel{\text{read column by column}}{\rightarrow}$$
Read the text once again column by column from the block, which is the resulting ciphertex:

 TTMTS ARIII NOSHP