Charge and reduce: A fixed-parameter algorithm for String-to-String Correction

String distance problems typically ask for a minimum number of permitted operations to transform one string into another. Such problems find application in a wide variety of areas, including error-correcting codes, parsing theory, speech recognition, and computational biology, to name a few. Here we consider a classic string distance problem, the NPNP-complete String-to-String Correction problem, first studied by Wagner some 35 years ago. In this problem, we are asked whether it is possible to transform string xx into string yy with at most kk operations on xx, where permitted operations are single-character deletions and adjacent character exchanges. We prove that String-to-String Correction is fixed-parameter tractable, for parameter kk, and present a simple fixed-parameter algorithm that solves the problem in O(2kn)O(2kn) time. We also devise a bounded search tree algorithm, and introduce a bookkeeping technique that we call charge and reduce  . This leads to an algorithm whose running time is O(1.6181kn)O(1.6181kn).