Does a similar result hold, if we don't consider inserts, deletions and substitutions (definition of edit distance), but only inserts and deletions?
Again, I know that's not precisely what you asked. I can't think of a reduction from "insert+delete only" problems to "insert+delete+subst" (all operations cost 1) problems (where solving the latter gives you a solution to the former, and the size is no more than k times the original).
Eg. what's the edit distance between these two strings?
AAAA BBBB
Traditionally, it would be 4, but it's unclear if you allow only inserts and deletions.
> Eg. what's the edit distance between these two strings?
>
> AAAA BBBB
>
> Traditionally, it would be 4, but it's unclear if you
> allow only inserts and deletions.
It is very easy to generalize the Wagner-Fisher algorithm (https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorit...) to this "simpler" variant of edit distance, but this algorithm will still have a (worst-case) runtime of O(m*n), where m, n are the lengths of the two strings.
Of course, the question remains: Is there a (worst-case) faster algorithm?