Circuit hamiltonien pour une famille de graphiques

Question

Pour $ sigma = {a, b } $, soit $ s_n = {w mid w in sigma ^ {*} land | w | = n } $.

Soit $ c_n sous-ensemble Sigma ^ {*} $ le langage des chaînes circulaires qui contiennent sous forme de sous-chaînes tous les éléments de $ s_n $. Par exemple, $ bbaaaababaabbbba in c_4 $

J'ai formulé le problème de la recherche du sous-ensemble de $ c_n $, formé par les chaînes circulaires avec le plus petite taille ($ = 2 ^ n $), comme le problème de la recherche de tous les circuits hamiltoniens sur le graphique qui a les éléments de $ s_n $ comme sommets, et les bords reliant toutes les paires de sommets $ s_i $ et $ s_j $ que $ s_i = xw $ et $ s_j = wy $, avec $ w in Sigma ^ {n-1} $ et $ x, y in Sigma $.

Pour l'exemple ci-dessus, le graphique pourrait ressembler à ceci:

Ma question:

Y aurait-il une solution en temps polynomial pour le problème du circuit de Hamilton limité à cette famille de graphiques?