5
$\begingroup$

For $\Sigma = \{a,b\}$, let $S_n = \{w\mid w \in \Sigma^{*} \land |w| = n\}$.

Let $C_n \subset \Sigma^{*}$ be the language of circular strings that contain as substrings all elements of $S_n$. For instance, $bbaaaababaabbbba \in C_4$

I have formulated the problem of finding the subset of $C_n$, formed by the circular strings with the smallest size ($=2^n$), as the problem of finding all hamiltonian circuits on the graph that has the elements of $S_n$ as vertices, and edges connecting all pairs of vertices $s_i$ and $s_j$ such that $s_i = xw$ and $s_j = wy$, with $w \in \Sigma^{n-1}$ and $x,y \in \Sigma$.

For the example above, the graph could look like this:

enter image description here

My question:

Would there be a polynomial-time solution for the hamilton circuit problem restricted to this family of graphs?

$\endgroup$
  • $\begingroup$ It feels like this might be related to $n$-ary Grey codes, which are a way of enumerating the length-$k$ strings from an $n$-symbol alphabet such that adjacent elements of the enumeration differ by exactly one character. That's not quite what you want but it's similar. (Yuval's answer appeared while I was writing this comment; I'm posting the comment anyway in case it turns out to be useful.) $\endgroup$ – David Richerby May 16 '15 at 14:45
4
$\begingroup$

This graph is known as a de Bruijn graph, and its Hamiltonian circuits are known as de Bruijn sequences. Both are well understood (for example, we know exactly how many of these exist).

$\endgroup$
  • 2
    $\begingroup$ In particular, every de Bruijn graph is Hamiltonian. $\endgroup$ – David Richerby May 16 '15 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.