String homomorphism is a function $h: \Sigma \to \Sigma^*$, which naturally defines a homomorphism on strings from $\Sigma^*$ with respect to concatenation. We denote $H(s) = h(s_1)h(s_2)\dots h(s_n)$ for $s \in \Sigma^*$, $s = s_1 s_2 \dots s_n$.

It is known that the problem "Given two strings $s$, $t$, decide whether there exist a homomorphism $h$ such that $H(s) = t$" is NP-complete. However, this problem seems also interesting when the alphabet of $s$ is small.

Now I allow a smaller alphabet for $s$ and thus redefine the homomorphism as a function $h: \Sigma \to Q^*$, where $|\Sigma| = k$, and let $s \in \Sigma^*$, $t \in Q^*$. Is now the problem of deciding the homomorphism existence known to be in FPT with the parameter $k$?

  • 2
    $\begingroup$ As a baseline: there's a simple $O(\textsf{poly}(|s|,|t|^k))$ algorithm to solve this, where one just tries all choices of $h$ with codomain the set of contiguous substrings of $t$. $\endgroup$ – Andrew Morgan Oct 4 '16 at 19:02

Your Answer

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

Browse other questions tagged or ask your own question.