2021/04/29 by Laurent Bulteau, Bulteau, Laurent, Michael R. Fellows +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2104.14171
openalex publication_date 2021/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study systems of String Equations where block variables need to be assigned strings so that their concatenation gives a specified target string. We investigate this problem under a multivariate complexity framework, searching for tractable special cases such as systems of equations with few block variables or few equations. Our main results include a polynomial-time algorithm for size-2 equations, and hardness for size-3 equations, as well as hardness for systems of two equations, even with tight constraints on the block variables. We also study a variant where few deletions are allowed in the target string, and give XP algorithms in this setting when the number of block variables is constant.