CLR cover
Previous problem

Problem 149: An application of linearly generated words

Next problem
\( \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \newcommand{\Cyc}{\mathsf{CycF}}% \newcommand{\PN}{\mathsf{LFSR'}}% \newcommand{\LFSR}{\mathsf{LFSR}}% \newcommand{\GEN}{\mathsf{GEN}}% \)

In this problem we want to decompose each binary de Bruijn graph $G_{n+1}$, disregarding two loops, into two edge-disjoint simple cycle. The word "simple" means that nodes do not repeat on the cycle. It is easy to see that each cycle should be of length $2^n-1$. LFSR-sequences provide a surprisingly simple algorithm.

Assume the alphabet is $\{0,1\}$. Denote by $\Cyc_m(w)$ the set of cycli c length-$m$ factors of a word $w$. A word of length $2^{n}$ is a de Bruijn word (deB word, in short) of rank $n$ if $\Cyc_n(w)=2^n$. We say that a word $w$ is a semi-deBruijn word of rank $n$ if $|w|=2^n-1$ and $\Cyc_n(w)=2^n-1$. Two semi-deBruijn words $u,w$ are orthogonal if $\Cyc_{n+1}(w)\, \cap\, \Cyc_{n+1}(u) \,=\, \emptyset$. We are interested in finding two orthogonal semi-deBruijn words $u,w$. Each of $u,w$ should contain cyclically all words of length $n$ except one, and together they contain all words of length $n+1$ except $0^{n+1}\, 1^{n+1}$.

A simple cycle of length $2^n-1$ in $G_n$ is called a semi-Hamiltonian cycle. Orthogonal semi-deBruijn words correspond to such cycles. The figure shows the decomposition of the graph $G_5$ without loops into two edge-disjoint semi-Hamiltonian cycles.

Semi-Hamiltonian cycles

We refer to problems Problem 18 and Problem 69 for the formal definition of de Bruijn graph $G_{n+1}$. The nodes of $G_{n+1}$ are words of length $n$, edges correspond to words of length $n+1$. The word $a_1a_2\cdots a_{n+1}$ corresponds to the edge $a_1a_2\cdots a_n \stackrel{a_{n+1}}{\rightarrow} a_2a_3\cdots a_{n+1}$. We discard two loops in the graph and ask to compute two semi-Hamiltonian cycle covering all non-loop edges. In the figure each node $i$ corresponds to the 4-bit binary representation of $i$.

Assume you have a primitive polynomial $W(x)$ over $Z_2$ of degree $n$. Compute two orthogonal semi-deBruijn words $u,w$. Equivalently, compute two edge-disjoint semi-Hamiltonian cycles in $G_{n+1}$ covering all non-loop edges.

Use LFSR-sequences.

References