<p>Computing this type of edit distance is NP-complete, which I will prove below by reducing from the NP-complete problem Vertex Cover (given a graph <span class="math-container">$G$</span> and a number <span class="math-container">$k$</span>, determine whether there exists a set of vertices <span class="math-container">$C$</span> with <span class="math-container">$|C|\le k$</span> such that each edge in <span class="math-container">$G$</span> has at least one vertex in <span class="math-container">$C$</span>, aka a vertex cover of size at most <span class="math-container">$k$</span>).</p>
<h1>Helpful subproblem</h1>
<p>Consider any sequence of edits between two strings (insertions/deletions/substitutions). This sequence of edits can be re-ordered so that the new sequence of edits has the same cost, but the substitutions happen after the insertions and deletions. We can separate the cost of the edits into two parts: an insertion/deletion cost and a substitution cost.</p>
<p>If you have already made a choice of what insertions/deletions to do starting at the source string, the insertion/deletion cost is already fixed, but there might be multiple different substitution strategies to get from that intermediate state to the target string. So one reasonable question is to ask what the optimal substitution strategy is at that point, and therefore what the optimal substitution cost is. Equivalently, this is asking for the edit distance using your distance metric but with only substitutions allowed.</p>
<p>So let's say we want to get from string <span class="math-container">$A = a_1a_2\ldots a_n$</span> to string <span class="math-container">$B = b_1b_2\ldots b_n$</span>. Construct the directed graph <span class="math-container">$T_{A\to B}$</span>, whose vertices are the characters used in these strings, and whose edges are the pairs <span class="math-container">$(u, v)$</span> such that <span class="math-container">$a_i = u \ne v = b_i$</span> for some <span class="math-container">$i$</span>. In other words, <span class="math-container">$T_{A\to B}$</span> is the graph of the desired substitutions.</p>
<p>Then we have the following <strong>key fact</strong>: The optimal substitution cost is equal to the number of vertices in <span class="math-container">$T_{A\to B}$</span> minus the number of acyclic weakly connected components of that graph. This fact will be used in the analysis of the reduction. The rest of this section will prove it. If you are just interested in the NP-hardness proof, feel free to skip to the next section.</p>
<p>We want to know what substitutions to do, but each substitution has cost 1 no matter how many times we do it. In other words, we can look at every pair of characters <span class="math-container">$(u,v)$</span>, and ask the question of whether we want to do the substitution of <span class="math-container">$u \to v$</span> at least once or not. This choice of which substitutions to do can be expressed as a directed graph, where we include edge <span class="math-container">$(u,v)$</span> if we plan to do the substitution of <span class="math-container">$u \to v$</span> at least once. Thus, the problem can be thought of as an optimization problem where we are looking for an optimal graph. What are we optimizing and what are our constraints? Well we are trying to minimize the substitution cost, so we are trying to choose a graph with a minimum possible number of edges. As for the constraints, each edge <span class="math-container">$(u,v)$</span> of <span class="math-container">$T_{A\to B}$</span> is a constraint saying that character <span class="math-container">$u$</span> must be converted into <span class="math-container">$v$</span> via a sequence of substitutions. In other words, the presence of edge <span class="math-container">$(u,v)$</span> in <span class="math-container">$T_{A\to B}$</span> means that we have the constraint that there must be a path from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> in our graph.</p>
<p>Consider any weakly connected component of a candidate graph for this graph optimization problem. If the component is acyclic, then there must be at least <span class="math-container">$n-1$</span> edges where <span class="math-container">$n$</span> is the number of vertices in that component. On the other hand, if the component is cyclic, there must be at least <span class="math-container">$n$</span> edges. Therefore, the overall number of edges in a candidate graph has as a lower bound the number of vertices (which is fixed) minus the number of acyclic weakly connected components (which can vary among candidate graphs). If we could get an upper bound on the number of acyclic weakly connected components, we would have an overall lower bound on the number of edges (aka the substitution cost).</p>
<p>Now consider a weakly connected component of <span class="math-container">$T_{A\to B}$</span>. If two vertices are in the same weakly connected component of <span class="math-container">$T_{A\to B}$</span>, then they must also be in the same connected component of any candidate graph in our graph optimization problem (because edges in <span class="math-container">$T_{A\to B}$</span> correspond to paths in the candidate graph, thereby retaining connectivity). Therefore, each weakly connected component of our candidate graph must be a union of weakly connected components of <span class="math-container">$T_{A\to B}$</span>. Thus, we see that the number of acyclic weakly connected components in <span class="math-container">$T_{A\to B}$</span> is an upper bound on the number of acyclic weakly connected components in our candidate graphs, which is exactly what we wanted. We have our lower bound on the substitution cost: it is at least the number of vertices in <span class="math-container">$T_{A\to B}$</span> minus the number of acyclic weakly connected components.</p>
<p>This is exactly the value that the key fact says is the optimal substitution cost, so all that's left is to demonstrate that this value can be achieved. We will do this as follows. Consider every acyclic weakly connected component of <span class="math-container">$T_{A\to B}$</span>, one at a time. That component is a DAG, so we can find a topological sort. Then, we can include that topological sort as a path in our graph of substitutions (i.e. earliest element in the sort points to second earliest, etc...). This uses one fewer edge than the number of vertices in that component. It also satisfies the constraints for that component: if <span class="math-container">$u$</span> needs to be converted into <span class="math-container">$v$</span>, then <span class="math-container">$(u,v)$</span> is an edge in the component; as a result <span class="math-container">$u$</span> must be before <span class="math-container">$v$</span> in the topological sort, and so the path of substitutions has as a subpath a path from <span class="math-container">$u$</span> to <span class="math-container">$v$</span>. After doing this for all the acyclic weakly connected components, take all the other vertices, and arrange them in a cycle. This uses a number of edges equal to the number of vertices and satisfies the requirement since any of these vertices has a path to any other (by following the cycle). This graph satisfies all the requirements and has a total number of edges equal to the number of vertices minus the number of acyclic weakly connected components.</p>
<p>This concludes the proof of the key fact.</p>
<h1>NP-hardness reduction</h1>
<p>We wish to prove that computing the edit distance is NP-hard by reducing from Vertex Cover. That means our reduction starts with a given Vertex Cover instance: a graph <span class="math-container">$G$</span> and a number <span class="math-container">$k$</span>. The reduction will output a pair of strings <span class="math-container">$(A, B)$</span> and a number <span class="math-container">$k'$</span> using polynomial time to compute these outputs. We will prove that the edit distance between <span class="math-container">$A$</span> and <span class="math-container">$B$</span> is at most <span class="math-container">$k'$</span> if and only if <span class="math-container">$G$</span> has a vertex cover of size at most <span class="math-container">$k$</span>.</p>
<p>In particular, <span class="math-container">$k'$</span> will be <span class="math-container">$k + 4m$</span> where <span class="math-container">$m$</span> is the number of edges in <span class="math-container">$G$</span>.</p>
<p>As for the strings <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, we will construct them out of several pieces <span class="math-container">$A = A_1A_2\ldots A_t, B = B_1B_2\ldots B_t$</span>, where each pair <span class="math-container">$(A_i, B_i)$</span> is a gadget built for a specific purpose. The rest of this section will go over what kinds of gadgets we will use, how these gadgets will be combined together (i.e. how many of which gadget we will use and what characters will be used for the gadgets), and then a correctness proof showing that this reduction is correct (i.e. the edit distance between <span class="math-container">$A$</span> and <span class="math-container">$B$</span> is at most <span class="math-container">$k'$</span> if and only if <span class="math-container">$G$</span> has a vertex cover of size at most <span class="math-container">$k$</span>).</p>
<h2>Gadgets</h2>
<p>The first kind of gadget we will use is an alignment gadget. This gadget consists of pair <span class="math-container">$(A_i, B_i)$</span> where <span class="math-container">$A_i$</span> consists of a large number of different characters that are not used anywhere else in <span class="math-container">$A$</span> or <span class="math-container">$B$</span> and <span class="math-container">$B_i = A_i$</span>. The purpose of this gadget is to force alignment of these two sections of strings <span class="math-container">$A$</span> and <span class="math-container">$B$</span> via insertions/deletions. If these two sections don't align, then in the substitution step, there would need to be a number of different substitutions roughly equal to the number of characters in <span class="math-container">$A_i$</span>. By making the number of characters large (much larger than <span class="math-container">$k'$</span>), we can make it prohibitively expensive, in terms of substitution cost, to not align these sections of <span class="math-container">$A$</span> and <span class="math-container">$B$</span> during the insertion/deletion stage of the edits.</p>
<p>We will use alignment gadgets as separators between the other gadgets, which allows us to reason about each other gadget <span class="math-container">$(A_i, B_i)$</span> in isolation. That is, we will be forced, due to separator gadgets <span class="math-container">$(A_{i-1},B_{i-1})$</span> and <span class="math-container">$(A_{i+1},B_{i+1})$</span>, to edit <span class="math-container">$A_i$</span> directly into <span class="math-container">$B_i$</span> (rather than possibly converting <span class="math-container">$A_i$</span> into some other part of string <span class="math-container">$B$</span> and converting some other part of <span class="math-container">$A$</span> into <span class="math-container">$B_i$</span>).</p>
<p>The second gadget is a forced substitution gadget. This gadget simply consists of <span class="math-container">$(A_i, B_i)$</span> where <span class="math-container">$A_i$</span> and <span class="math-container">$B_i$</span> have the same (very large) length, <span class="math-container">$A_i$</span> consists entirely of copies of one character <span class="math-container">$u$</span> and <span class="math-container">$B_i$</span> consists of entirely copies of another character <span class="math-container">$v$</span>. The duplication of these characters many times makes it so that even after using an insertion/deletion cost of up to <span class="math-container">$k'$</span>, there is still at least one character <span class="math-container">$u$</span> that must be converted into a <span class="math-container">$v$</span>. Since that conversion needs to happen anyway, the simplest way to solve this gadget is to just use a substitution cost of 1 to convert all the copies of <span class="math-container">$u$</span> into copies of <span class="math-container">$v$</span>. However, it is possible to use some other substitution strategy to convert these characters (i.e. by converting to some third character before converting to <span class="math-container">$u$</span>). All we really need to know here is that the insertion/deletion cost within this gadget can be as low as 0 and that the desired substitution <span class="math-container">$u \to v$</span> is forced, either directly or indirectly, by this gadget.</p>
<p>The final gadget is a choice gadget. Here <span class="math-container">$A_i = x_1ax_2$</span> and <span class="math-container">$B_i = bc$</span>, where <span class="math-container">$x_1$</span> and <span class="math-container">$x_2$</span> are characters unique to this gadget (not used anywhere else), while <span class="math-container">$a$</span>, <span class="math-container">$b$</span>, and <span class="math-container">$c$</span> are characters potentially used elsewhere. Assuming this gadget is placed between two alignment gadgets, we need to convert <span class="math-container">$A_i$</span> into <span class="math-container">$B_i$</span>. If this is done with an insertion/deletion cost of <span class="math-container">$1$</span>, then we are left trying to convert either <span class="math-container">$x_1a$</span>, <span class="math-container">$x_1x_2$</span>, or <span class="math-container">$ax_2$</span> into <span class="math-container">$bc$</span>. This can be accomplished with two substitutions, though the substitution cost can be anywhere between <span class="math-container">$0$</span> and <span class="math-container">$2$</span> depending on whether these substitutions can also be used elsewhere. Therefore, if using an insertion/deletion cost of <span class="math-container">$1$</span>, the total cost in this gadget is at most <span class="math-container">$3$</span>. On the other hand, the next smallest possible insertion/deletion cost in this gadget is <span class="math-container">$3$</span>, which is already at least the cost of the three solutions listed above. Therefore, there is always an efficient solution of this gadget with only one deletion followed by substitutions. If we chose to delete <span class="math-container">$a$</span> and substitute <span class="math-container">$x_1x_2$</span> into <span class="math-container">$bc$</span>, then both substitutions have cost <span class="math-container">$1$</span> since neither <span class="math-container">$x_1$</span> nor <span class="math-container">$x_2$</span> appear elsewhere in the strings; therefore, if we were to instead choose one of the other two possible deletions, the cost would be no worse. That is why this is a choice gadget: the remaining two choices involve either substituting <span class="math-container">$a$</span> into <span class="math-container">$b$</span> (when <span class="math-container">$ax_2 \to bc$</span>) or into <span class="math-container">$c$</span> (when <span class="math-container">$x_1a \to bc$</span>).</p>
<h2>Arrangement of gadgets</h2>
<p>As previously mentioned, we will use alignment gadgets as separators for all the other gadgets. In other words, every second gadget will be an alignment gadget. This leaves the question of which other gadgets should be used.</p>
<p>Consider every edge <span class="math-container">$e$</span> in <span class="math-container">$G$</span>. We will use two characters <span class="math-container">$p_e$</span> and <span class="math-container">$q_e$</span> for this edge. For each such edge <span class="math-container">$e$</span>, we will include two forced substitution gadgets forcing the substitution of <span class="math-container">$p_e$</span> into <span class="math-container">$q_e$</span> and the substitution of <span class="math-container">$q_e$</span> into <span class="math-container">$p_e$</span>.</p>
<p>Next consider the vertices of <span class="math-container">$G$</span>. If <span class="math-container">$v$</span> is a vertex, we will use <span class="math-container">$r_v$</span> as a character. For every edge <span class="math-container">$e = (u, v)$</span>, we will create a choice gadget in which character <span class="math-container">$p_e$</span> must be substituted into either <span class="math-container">$r_u$</span> or <span class="math-container">$r_v$</span> (i.e. the choice gadget where <span class="math-container">$A_i = x_1p_ex_2$</span> and <span class="math-container">$B_i = r_ur_v$</span>).</p>
<p>That concludes the actual construction of the reduction. Notably, these strings <span class="math-container">$A$</span> and <span class="math-container">$B$</span> and the value <span class="math-container">$k$</span> can easily be constructed from the vertex cover instance in polynomial time. What's left is to prove the correctness.</p>
<h2>Correctness</h2>
<p>Suppose first that we have a vertex cover <span class="math-container">$C$</span> of <span class="math-container">$G$</span> with <span class="math-container">$|C| \le k$</span>. Then we will prove that the edit distance between <span class="math-container">$A$</span> and <span class="math-container">$B$</span> will be less than <span class="math-container">$k' = k + 4m$</span>.</p>
<p><span class="math-container">$A$</span> can be edited into <span class="math-container">$B$</span> as follows:</p>
<ul>
<li>First, in the insertion/deletion step, delete one character from each choice gadget, for an insertion/deletion cost of <span class="math-container">$m$</span>. In particular, for each edge <span class="math-container">$e = (u,v)$</span>, we have the gadget <span class="math-container">$(A_i, B_i) = (x_1p_ex_2, r_ur_v)$</span> and we will delete either <span class="math-container">$x_1$</span> or <span class="math-container">$x_2$</span> as follows. Either <span class="math-container">$u$</span> or <span class="math-container">$v$</span> is in the vertex cover <span class="math-container">$C$</span>. We will delete <span class="math-container">$x_1$</span> (thus requiring the substitution <span class="math-container">$p_e \to r_u$</span>) if <span class="math-container">$u \in C$</span>, and will delete <span class="math-container">$x_2$</span> (thus requiring the substitution <span class="math-container">$p_e \to r_v$</span>) otherwise (in which case <span class="math-container">$v \in C$</span>).</li>
<li>In the substitution step, we will do two things. First, we will look at each choice gadget, and we will convert either <span class="math-container">$x_1$</span> or <span class="math-container">$x_2$</span>, whichever is still there, into the character it needs to turn into. This has a substitution cost of <span class="math-container">$m$</span>. Second, we will take the characters <span class="math-container">$p_e$</span> and <span class="math-container">$q_e$</span> for every edge <span class="math-container">$e$</span> in <span class="math-container">$G$</span> and the characters <span class="math-container">$r_v$</span> for every vertex <span class="math-container">$v$</span> in <span class="math-container">$C$</span>, and we will arrange these characters in a cycle, substituting each character for the next in the cycle. This has a substitution cost of <span class="math-container">$2m + |C|$</span>, and allows any of these characters to turn into any other (by simply substituting along the cycle repeatedly).</li>
</ul>
<p>This converts <span class="math-container">$A$</span> into <span class="math-container">$B$</span> with a total cost of <span class="math-container">$m+m+2m+|C| = 4m + |C| \le 4m + k = k'$</span>. To confirm that this actually converts <span class="math-container">$A$</span> into <span class="math-container">$B$</span>, lets consider every gadget. The alignment gadgets are successfully converted as long as the other gadgets are. The forced substitution gadgets are successfully converted since both <span class="math-container">$p_e$</span> and <span class="math-container">$q_e$</span> are in the cycle of substitutions. As for the choice gadgets, the necessary substitutions are either <span class="math-container">$x_1p_e \to r_ur_v$</span> (in a case where <span class="math-container">$v \in C$</span>) or <span class="math-container">$p_ex_2 \to r_ur_v$</span> (when <span class="math-container">$u \in C$</span>). The substitutions of <span class="math-container">$x_1$</span> or <span class="math-container">$x_2$</span> are explicitly handled. Therefore, we're left needing to substitute either <span class="math-container">$p_e \to r_v$</span> (when <span class="math-container">$v \in C$</span>) or <span class="math-container">$p_e \to r_u$</span> (when <span class="math-container">$u \in C$</span>). Note that in both cases, the character that <span class="math-container">$p_e$</span> needs to be converted into is in the cycle of substitutions, meaning that the above instructions successfully convert the choice gadgets as well.</p>
<p>This shows that if the answer to the vertex cover instance is &quot;yes&quot;, then the edit distance between <span class="math-container">$A$</span> and <span class="math-container">$B$</span> is at most <span class="math-container">$k'$</span>.</p>
<p>What about the reverse direction?</p>
<p>Let's say there is a way to edit <span class="math-container">$A$</span> into <span class="math-container">$B$</span> using at most cost <span class="math-container">$k'$</span>. Suppose we have the solution with the least cost. When we analyzed the choice gadget, we saw that there is always an efficient (least cost) solution involving one deletion in that choice gadget, specifically deleting either <span class="math-container">$x_1$</span> or <span class="math-container">$x_2$</span> in the gadget. Thus we can assume WLOG that our least-cost solution has no insertions and exactly one deletion in each choice gadget and that the deletion is one of the two intended deletions. That's an insertion/deletion cost of <span class="math-container">$m$</span> in the choice gadgets alone. Therefore, the substitution cost must be at most <span class="math-container">$k' - m = 3m + k$</span>.</p>
<p>Due to the alignment gadgets we know that the choice gadgets must be solved entirely by substitution after the one deletion in that gadget. Therefore, for each edge <span class="math-container">$e = (u,v)$</span>, we either have a substitution of <span class="math-container">$x_1p_e \to r_ur_v$</span> or <span class="math-container">$p_ex_2 \to r_ur_v$</span>. Define a set of vertices <span class="math-container">$C$</span> such that <span class="math-container">$v \in C$</span> if and only if there is a substitution <span class="math-container">$p_e \to r_v$</span> that needs to happen in some edge gadget. By the above, we see that <span class="math-container">$C$</span> must be a vertex cover (since each edge gadget contributes one of the endpoints of the edge to <span class="math-container">$C$</span>).</p>
<p>We also know from the forced substitution gadgets that <span class="math-container">$p_e \to q_e$</span> and <span class="math-container">$q_e \to p_e$</span> are forced substitutions.</p>
<p>Let <span class="math-container">$A'$</span> be the state of the string after the insertion/deletion step and before the substitution step. At this point we will use the key fact from the first section to determine what the substitution cost must be. We know that there is a directed graph <span class="math-container">$T_{A'\to B}$</span> whose edges are the substitutions that are required to convert <span class="math-container">$A'$</span> into <span class="math-container">$B$</span>. We know from the above that this graph includes the following edges:</p>
<ul>
<li><span class="math-container">$(p_e, q_e)$</span> and <span class="math-container">$(q_e, p_e)$</span> for every edge <span class="math-container">$e$</span> in <span class="math-container">$G$</span></li>
<li>Either <span class="math-container">$(x_1, r_u)$</span> and <span class="math-container">$(p_e, r_v)$</span>, or <span class="math-container">$(x_2, r_v)$</span> and <span class="math-container">$(p_e, r_u)$</span> for each edge <span class="math-container">$e = (u,v)$</span> (where the <span class="math-container">$x_1$</span> and <span class="math-container">$x_2$</span> vertices are unique per edge <span class="math-container">$e$</span>)</li>
</ul>
<p>According to the key fact from the previous section, the substitution cost is equal to the number of vertices in this graph minus the number of acyclic weakly connected components. This value can never decrease if we add more vertices or edges, so computing this value for only those edges listed above is a lower bound on the substitution cost of our edit solution.</p>
<p>There are exactly <span class="math-container">$3m+n$</span> vertices listed above, where <span class="math-container">$n$</span> is the number of vertices in <span class="math-container">$G$</span> (one <span class="math-container">$p_e$</span> vertex per edge of <span class="math-container">$G$</span>, one <span class="math-container">$q_e$</span> vertex per edge of <span class="math-container">$G$</span>, one <span class="math-container">$x_1$</span> or <span class="math-container">$x_2$</span> per choice gadget--of which there are <span class="math-container">$m$</span>, and one <span class="math-container">$r_v$</span> per vertex of <span class="math-container">$G$</span>). What about the number of acyclic weakly connected components? Due to the cycle <span class="math-container">$p_e, q_e, p_e$</span>, the connected components of vertices <span class="math-container">$p_e$</span> are never acyclic. As for each <span class="math-container">$r_v$</span>, it either connects to some <span class="math-container">$p_e$</span>, in the case that <span class="math-container">$v \in C$</span>, or it does not connect to any <span class="math-container">$p_e$</span> if <span class="math-container">$v \not\in C$</span>. In the former case, this vertex is not in an acyclic weakly connected component. In the latter case, the entire weakly connected component of <span class="math-container">$r_v$</span> is that vertex with some number of <span class="math-container">$x_1$</span> or <span class="math-container">$x_2$</span> vertices neighboring it. That is acyclic. As for the <span class="math-container">$x_1$</span> or <span class="math-container">$x_2$</span> vertices, each one neighbors an <span class="math-container">$r_v$</span> vertex, and its weakly connected component has therefore already been addressed one way or the other above. Thus, we see that each acyclic weakly connected component contains exactly one <span class="math-container">$r_v$</span> vertex and furthermore one where <span class="math-container">$v \not\in C$</span>. Thus, the number acyclic weakly connected components is equal to the number of vertices <span class="math-container">$v$</span> not in <span class="math-container">$C$</span>. This equals <span class="math-container">$n - |C|$</span>.</p>
<p>The substitution cost therefore has a lower bound of <span class="math-container">$(3m+n) - (n-|C|) = 3m+|C|$</span>. But we saw before that the substitution cost must be at most <span class="math-container">$k' - m = 3m + k$</span>. Therefore, we see that it must be the case that <span class="math-container">$|C| \le k$</span>. Then <span class="math-container">$C$</span> is a vertex cover of size at most <span class="math-container">$k$</span>, proving that the answer to the vertex cover instance is &quot;yes&quot;.</p>
<p>We have shown via the two directions that <span class="math-container">$G$</span> has a vertex cover of size at most <span class="math-container">$k$</span> if and only if <span class="math-container">$A$</span> and <span class="math-container">$B$</span> have an edit distance of at most <span class="math-container">$k'$</span>. This proves that the reduction is correct. Since we previously noted that it runs in polynomial time, this concludes the proof that computing edit distance (as you defined it) is NP-hard.</p>

CC BY-SA 4.0
2020-12-18T11:32:41.977Z
Very nice! Thank you. At least my question wasn't too trivial :)
Simd
CC BY-SA 4.0
2020-12-18T11:07:09.270Z
2020-12-18T11:07:09.270Z
Mikhail Rudoy
<p>This question is about the following variant of <a href="https://en.wikipedia.org/wiki/Levenshtein_distance#:%7E:text=Informally%2C%20the%20Levenshtein%20distance%20between,considered%20this%20distance%20in%201965." rel="nofollow noreferrer">edit distance</a>.  Say we have a cost of 1 for inserts, deletes and substitutions as usual with one exception. A substitution for a given letter <code>x</code> for a letter <code>y</code> only costs <code>1</code> the first time.  Any further substitutions of <code>x</code> for <code>y</code> cost 0.</p>
<p>As simple examples:</p>
<pre><code>A = apppple
B = attttle
</code></pre>
<p>cost 1 (not 4) to transform A into B. This is because we change <code>p</code> for a <code>t</code> four times but we only charge for the first one.</p>
<pre><code>A = apxpxple
B = atxyxtle
</code></pre>
<p>cost 2 (not 3) as the <code>p</code> to <code>t</code> substitution only costs 1 even though we do it twice.</p>
<pre><code>A = apppple
B = altttte
</code></pre>
<p>cost 2. <code>p</code> -&gt; <code>l</code> give <code>allllle</code> and then <code>l</code> -&gt; <code>t</code> gives <code>altttte</code>.</p>
<p>If we assume the total length of the input is <code>n</code>, what is the best time complexity?</p>
<p>I suspect the problem is NP-hard so I am not expecting a poly time solution.</p>
<p>Question previously asked at <a href="https://codegolf.stackexchange.com/questions/215148/edit-distance-where-a-substitution-only-costs-the-first-time">https://codegolf.stackexchange.com/questions/215148/edit-distance-where-a-substitution-only-costs-the-first-time</a></p>

CC BY-SA 4.0
2020-11-22T06:11:01.547Z
Can you find a case where the sequence of operations found with the regular Levenshtein distance is not also optimal for this problem?
causative
CC BY-SA 4.0
2020-11-22T06:34:58.357Z
Is the size of the alphabet constant?  There's a straightforward dynamic programming algorithm whose running time is something like $O(n^2 2^{|\Sigma|^2})$, which is $O(n^2)$ if $|\Sigma|$ is a constant.
D.W.
CC BY-SA 4.0
2020-11-22T07:06:20.630Z
@D.W. I should have said, we should assume the alphabet size can be as large as n.
Simd
CC BY-SA 4.0
2020-11-22T07:40:57.247Z
My intuition says that it can be done in polynomial time, but I am too lazy to think of a way.
user21820
CC BY-SA 4.0
2020-11-22T12:15:02.020Z
@user21820 Even an O(2^n) time solution is not obvious to me.
Simd
CC BY-SA 4.0
2020-11-22T16:36:15.570Z
Hmm. My intuition could be wrong... hopefully someone else who comes along can settle your question. =)
user21820
CC BY-SA 4.0
2020-11-23T11:51:06.800Z
@causative It's a good question which is also a little subtle. Take A = 00001111 and B = 11112222.   For edit distance we delete the first 4 digits and insert 4 digits for a cost of 8. In my measure we can substitute 1->2 and 0->1 for a cost of 2. But in the edit distance case we could also have done 8 substitutions for the same cost of 8. The point being that there can be many different sets of operations that have the same result and same cost.
Simd
CC BY-SA 4.0
2020-12-16T11:07:28.913Z
@Anush, doesn't your third example have cost 2? Here's my sequence: $apppple \to allllle \to altttte$.

Also, what would the cost of this other example be: $aabbcc \to bccaab$? I believe the answer should be 3 (sequence $aabbcc \to babbcc \to bbbbcc \to bcbbcc \to bccbcc \to bccccc \to bccacc \to bccaac \to bccaaa \to bccaab$, using only transitions $a\to b$, $b\to c$, and $c\to a$), but I want to make sure that this matches your intention with this problem.

If my costs are correct, then I'll post an NP-hardness proof. If I'm wrong, then could you please edit the problem to clarify why?
Mikhail Rudoy
CC BY-SA 4.0
2020-12-16T20:23:26.860Z
@MikhailRudoy You are right about example 3,  thank you. I will fix that.  For your example don't you end up at bccaaa if you just do a->b, b->c, c->a? You seem to be missing the final step to get to bccaab.
Simd
CC BY-SA 4.0
2020-12-17T14:27:58.880Z
The final step (to get from bccaaa to bccaab) is to just do one last a->b substitution, which is free because there has previously been an a->b substitution. 

I suspect you are thinking of the problem in terms of "batches" of substitutions (multiple consecutive substitutions of the same characters). Then the cost is just the number of batches. My point in bringing up this example is exactly to show the difference between that batching cost function and the cost function you described above, where non-consecutive repetitions also share their cost of 1.
Mikhail Rudoy
CC BY-SA 4.0
2020-12-17T18:23:41.123Z
@Mikhailardoy good point. Do you think one of these versions is np hard? I prefer your version.
Simd
CC BY-SA 4.0
2020-12-18T11:07:43.120Z
Yep. I posted my answer :)
Mikhail Rudoy
<ds.algorithms><edit-distance>
Time complexity for a variant of edit distance
Simd
# Time complexity for a variant of edit distance

(Asked by: username_0 on 2020-11-21)

This question is about the following variant of edit distance.  Say we have a cost of 1 for inserts, deletes and substitutions as usual with one exception. A substitution for a given letter x for a letter y only costs 1 the first time.  Any further substitutions of x for y cost 0.
As simple examples:
A = apppple
B = attttle

cost 1 (not 4) to transform A into B. This is because we change p for a t four times but we only charge for the first one.
A = apxpxple
B = atxyxtle

cost 2 (not 3) as the p to t substitution only costs 1 even though we do it twice.
A = apppple
B = altttte

cost 2. p -> l give allllle and then l -> t gives altttte.
If we assume the total length of the input is n, what is the best time complexity?
I suspect the problem is NP-hard so I am not expecting a poly time solution.
Question previously asked at https://codegolf.stackexchange.com/questions/215148/edit-distance-where-a-substitution-only-costs-the-first-time

**Tags:** ds.algorithms, edit-distance

> **Comments:**
> **username_1**: Can you find a case where the sequence of operations found with the regular Levenshtein distance is not also optimal for this problem?  
> **username_2**: Is the size of the alphabet constant?  There's a straightforward dynamic programming algorithm whose running time is something like $O(n^2 2^{|\Sigma|^2})$, which is $O(n^2)$ if $|\Sigma|$ is a constant.  
> **username_0**: @username_2 I should have said, we should assume the alphabet size can be as large as n.  
> **username_3**: My intuition says that it can be done in polynomial time, but I am too lazy to think of a way.  
> **username_0**: @username_3 Even an O(2^n) time solution is not obvious to me.  
> **username_3**: Hmm. My intuition could be wrong... hopefully someone else who comes along can settle your question. =)  
> **username_0**: @username_1 It's a good question which is also a little subtle. Take A = 00001111 and B = 11112222.   For edit distance we delete the first 4 digits and insert 4 digits for a cost of 8. In my measure we can substitute 1->2 and 0->1 for a cost of 2. But in the edit distance case we could also have done 8 substitutions for the same cost of 8. The point being that there can be many different sets of operations that have the same result and same cost.  
> **username_4**: @Anush, doesn't your third example have cost 2? Here's my sequence: $apppple \to allllle \to altttte$.  Also, what would the cost of this other example be: $aabbcc \to bccaab$? I believe the answer should be 3 (sequence $aabbcc \to babbcc \to bbbbcc \to bcbbcc \to bccbcc \to bccccc \to bccacc \to bccaac \to bccaaa \to bccaab$, using only transitions $a\to b$, $b\to c$, and $c\to a$), but I want to make sure that this matches your intention with this problem.  If my costs are correct, then I'll post an NP-hardness proof. If I'm wrong, then could you please edit the problem to clarify why?  
> **username_0**: @MikhailRudoy You are right about example 3,  thank you. I will fix that.  For your example don't you end up at bccaaa if you just do a->b, b->c, c->a? You seem to be missing the final step to get to bccaab.  
> **username_4**: The final step (to get from bccaaa to bccaab) is to just do one last a->b substitution, which is free because there has previously been an a->b substitution.   I suspect you are thinking of the problem in terms of "batches" of substitutions (multiple consecutive substitutions of the same characters). Then the cost is just the number of batches. My point in bringing up this example is exactly to show the difference between that batching cost function and the cost function you described above, where non-consecutive repetitions also share their cost of 1.  
> **username_0**: @Mikhailardoy good point. Do you think one of these versions is np hard? I prefer your version.  
> **username_4**: Yep. I posted my answer :)  

---

## 1 answers

### Answer by username_4 on 2020-12-18. Score: 6

Computing this type of edit distance is NP-complete, which I will prove below by reducing from the NP-complete problem Vertex Cover (given a graph $G$ and a number $k$, determine whether there exists a set of vertices $C$ with $|C|\le k$ such that each edge in $G$ has at least one vertex in $C$, aka a vertex cover of size at most $k$).

# Helpful subproblem

Consider any sequence of edits between two strings (insertions/deletions/substitutions). This sequence of edits can be re-ordered so that the new sequence of edits has the same cost, but the substitutions happen after the insertions and deletions. We can separate the cost of the edits into two parts: an insertion/deletion cost and a substitution cost.

If you have already made a choice of what insertions/deletions to do starting at the source string, the insertion/deletion cost is already fixed, but there might be multiple different substitution strategies to get from that intermediate state to the target string. So one reasonable question is to ask what the optimal substitution strategy is at that point, and therefore what the optimal substitution cost is. Equivalently, this is asking for the edit distance using your distance metric but with only substitutions allowed.

So let's say we want to get from string $A = a\_1a\_2\ldots a\_n$ to string $B = b\_1b\_2\ldots b\_n$. Construct the directed graph $T\_{A\to B}$, whose vertices are the characters used in these strings, and whose edges are the pairs $(u, v)$ such that $a\_i = u \ne v = b\_i$ for some $i$. In other words, $T\_{A\to B}$ is the graph of the desired substitutions.

Then we have the following **key fact**: The optimal substitution cost is equal to the number of vertices in $T\_{A\to B}$ minus the number of acyclic weakly connected components of that graph. This fact will be used in the analysis of the reduction. The rest of this section will prove it. If you are just interested in the NP-hardness proof, feel free to skip to the next section.

We want to know what substitutions to do, but each substitution has cost 1 no matter how many times we do it. In other words, we can look at every pair of characters $(u,v)$, and ask the question of whether we want to do the substitution of $u \to v$ at least once or not. This choice of which substitutions to do can be expressed as a directed graph, where we include edge $(u,v)$ if we plan to do the substitution of $u \to v$ at least once. Thus, the problem can be thought of as an optimization problem where we are looking for an optimal graph. What are we optimizing and what are our constraints? Well we are trying to minimize the substitution cost, so we are trying to choose a graph with a minimum possible number of edges. As for the constraints, each edge $(u,v)$ of $T\_{A\to B}$ is a constraint saying that character $u$ must be converted into $v$ via a sequence of substitutions. In other words, the presence of edge $(u,v)$ in $T\_{A\to B}$ means that we have the constraint that there must be a path from $u$ to $v$ in our graph.

Consider any weakly connected component of a candidate graph for this graph optimization problem. If the component is acyclic, then there must be at least $n-1$ edges where $n$ is the number of vertices in that component. On the other hand, if the component is cyclic, there must be at least $n$ edges. Therefore, the overall number of edges in a candidate graph has as a lower bound the number of vertices (which is fixed) minus the number of acyclic weakly connected components (which can vary among candidate graphs). If we could get an upper bound on the number of acyclic weakly connected components, we would have an overall lower bound on the number of edges (aka the substitution cost).

Now consider a weakly connected component of $T\_{A\to B}$. If two vertices are in the same weakly connected component of $T\_{A\to B}$, then they must also be in the same connected component of any candidate graph in our graph optimization problem (because edges in $T\_{A\to B}$ correspond to paths in the candidate graph, thereby retaining connectivity). Therefore, each weakly connected component of our candidate graph must be a union of weakly connected components of $T\_{A\to B}$. Thus, we see that the number of acyclic weakly connected components in $T\_{A\to B}$ is an upper bound on the number of acyclic weakly connected components in our candidate graphs, which is exactly what we wanted. We have our lower bound on the substitution cost: it is at least the number of vertices in $T\_{A\to B}$ minus the number of acyclic weakly connected components.

This is exactly the value that the key fact says is the optimal substitution cost, so all that's left is to demonstrate that this value can be achieved. We will do this as follows. Consider every acyclic weakly connected component of $T\_{A\to B}$, one at a time. That component is a DAG, so we can find a topological sort. Then, we can include that topological sort as a path in our graph of substitutions (i.e. earliest element in the sort points to second earliest, etc...). This uses one fewer edge than the number of vertices in that component. It also satisfies the constraints for that component: if $u$ needs to be converted into $v$, then $(u,v)$ is an edge in the component; as a result $u$ must be before $v$ in the topological sort, and so the path of substitutions has as a subpath a path from $u$ to $v$. After doing this for all the acyclic weakly connected components, take all the other vertices, and arrange them in a cycle. This uses a number of edges equal to the number of vertices and satisfies the requirement since any of these vertices has a path to any other (by following the cycle). This graph satisfies all the requirements and has a total number of edges equal to the number of vertices minus the number of acyclic weakly connected components.

This concludes the proof of the key fact.

# NP-hardness reduction

We wish to prove that computing the edit distance is NP-hard by reducing from Vertex Cover. That means our reduction starts with a given Vertex Cover instance: a graph $G$ and a number $k$. The reduction will output a pair of strings $(A, B)$ and a number $k'$ using polynomial time to compute these outputs. We will prove that the edit distance between $A$ and $B$ is at most $k'$ if and only if $G$ has a vertex cover of size at most $k$.

In particular, $k'$ will be $k + 4m$ where $m$ is the number of edges in $G$.

As for the strings $A$ and $B$, we will construct them out of several pieces $A = A\_1A\_2\ldots A\_t, B = B\_1B\_2\ldots B\_t$, where each pair $(A\_i, B\_i)$ is a gadget built for a specific purpose. The rest of this section will go over what kinds of gadgets we will use, how these gadgets will be combined together (i.e. how many of which gadget we will use and what characters will be used for the gadgets), and then a correctness proof showing that this reduction is correct (i.e. the edit distance between $A$ and $B$ is at most $k'$ if and only if $G$ has a vertex cover of size at most $k$).

## Gadgets

The first kind of gadget we will use is an alignment gadget. This gadget consists of pair $(A\_i, B\_i)$ where $A\_i$ consists of a large number of different characters that are not used anywhere else in $A$ or $B$ and $B\_i = A\_i$. The purpose of this gadget is to force alignment of these two sections of strings $A$ and $B$ via insertions/deletions. If these two sections don't align, then in the substitution step, there would need to be a number of different substitutions roughly equal to the number of characters in $A\_i$. By making the number of characters large (much larger than $k'$), we can make it prohibitively expensive, in terms of substitution cost, to not align these sections of $A$ and $B$ during the insertion/deletion stage of the edits.

We will use alignment gadgets as separators between the other gadgets, which allows us to reason about each other gadget $(A\_i, B\_i)$ in isolation. That is, we will be forced, due to separator gadgets $(A\_{i-1},B\_{i-1})$ and $(A\_{i+1},B\_{i+1})$, to edit $A\_i$ directly into $B\_i$ (rather than possibly converting $A\_i$ into some other part of string $B$ and converting some other part of $A$ into $B\_i$).

The second gadget is a forced substitution gadget. This gadget simply consists of $(A\_i, B\_i)$ where $A\_i$ and $B\_i$ have the same (very large) length, $A\_i$ consists entirely of copies of one character $u$ and $B\_i$ consists of entirely copies of another character $v$. The duplication of these characters many times makes it so that even after using an insertion/deletion cost of up to $k'$, there is still at least one character $u$ that must be converted into a $v$. Since that conversion needs to happen anyway, the simplest way to solve this gadget is to just use a substitution cost of 1 to convert all the copies of $u$ into copies of $v$. However, it is possible to use some other substitution strategy to convert these characters (i.e. by converting to some third character before converting to $u$). All we really need to know here is that the insertion/deletion cost within this gadget can be as low as 0 and that the desired substitution $u \to v$ is forced, either directly or indirectly, by this gadget.

The final gadget is a choice gadget. Here $A\_i = x\_1ax\_2$ and $B\_i = bc$, where $x\_1$ and $x\_2$ are characters unique to this gadget (not used anywhere else), while $a$, $b$, and $c$ are characters potentially used elsewhere. Assuming this gadget is placed between two alignment gadgets, we need to convert $A\_i$ into $B\_i$. If this is done with an insertion/deletion cost of $1$, then we are left trying to convert either $x\_1a$, $x\_1x\_2$, or $ax\_2$ into $bc$. This can be accomplished with two substitutions, though the substitution cost can be anywhere between $0$ and $2$ depending on whether these substitutions can also be used elsewhere. Therefore, if using an insertion/deletion cost of $1$, the total cost in this gadget is at most $3$. On the other hand, the next smallest possible insertion/deletion cost in this gadget is $3$, which is already at least the cost of the three solutions listed above. Therefore, there is always an efficient solution of this gadget with only one deletion followed by substitutions. If we chose to delete $a$ and substitute $x\_1x\_2$ into $bc$, then both substitutions have cost $1$ since neither $x\_1$ nor $x\_2$ appear elsewhere in the strings; therefore, if we were to instead choose one of the other two possible deletions, the cost would be no worse. That is why this is a choice gadget: the remaining two choices involve either substituting $a$ into $b$ (when $ax\_2 \to bc$) or into $c$ (when $x\_1a \to bc$).

## Arrangement of gadgets

As previously mentioned, we will use alignment gadgets as separators for all the other gadgets. In other words, every second gadget will be an alignment gadget. This leaves the question of which other gadgets should be used.

Consider every edge $e$ in $G$. We will use two characters $p\_e$ and $q\_e$ for this edge. For each such edge $e$, we will include two forced substitution gadgets forcing the substitution of $p\_e$ into $q\_e$ and the substitution of $q\_e$ into $p\_e$.

Next consider the vertices of $G$. If $v$ is a vertex, we will use $r\_v$ as a character. For every edge $e = (u, v)$, we will create a choice gadget in which character $p\_e$ must be substituted into either $r\_u$ or $r\_v$ (i.e. the choice gadget where $A\_i = x\_1p\_ex\_2$ and $B\_i = r\_ur\_v$).

That concludes the actual construction of the reduction. Notably, these strings $A$ and $B$ and the value $k$ can easily be constructed from the vertex cover instance in polynomial time. What's left is to prove the correctness.

## Correctness

Suppose first that we have a vertex cover $C$ of $G$ with $|C| \le k$. Then we will prove that the edit distance between $A$ and $B$ will be less than $k' = k + 4m$.

$A$ can be edited into $B$ as follows:

* First, in the insertion/deletion step, delete one character from each choice gadget, for an insertion/deletion cost of $m$. In particular, for each edge $e = (u,v)$, we have the gadget $(A\_i, B\_i) = (x\_1p\_ex\_2, r\_ur\_v)$ and we will delete either $x\_1$ or $x\_2$ as follows. Either $u$ or $v$ is in the vertex cover $C$. We will delete $x\_1$ (thus requiring the substitution $p\_e \to r\_u$) if $u \in C$, and will delete $x\_2$ (thus requiring the substitution $p\_e \to r\_v$) otherwise (in which case $v \in C$).
* In the substitution step, we will do two things. First, we will look at each choice gadget, and we will convert either $x\_1$ or $x\_2$, whichever is still there, into the character it needs to turn into. This has a substitution cost of $m$. Second, we will take the characters $p\_e$ and $q\_e$ for every edge $e$ in $G$ and the characters $r\_v$ for every vertex $v$ in $C$, and we will arrange these characters in a cycle, substituting each character for the next in the cycle. This has a substitution cost of $2m + |C|$, and allows any of these characters to turn into any other (by simply substituting along the cycle repeatedly).

This converts $A$ into $B$ with a total cost of $m+m+2m+|C| = 4m + |C| \le 4m + k = k'$. To confirm that this actually converts $A$ into $B$, lets consider every gadget. The alignment gadgets are successfully converted as long as the other gadgets are. The forced substitution gadgets are successfully converted since both $p\_e$ and $q\_e$ are in the cycle of substitutions. As for the choice gadgets, the necessary substitutions are either $x\_1p\_e \to r\_ur\_v$ (in a case where $v \in C$) or $p\_ex\_2 \to r\_ur\_v$ (when $u \in C$). The substitutions of $x\_1$ or $x\_2$ are explicitly handled. Therefore, we're left needing to substitute either $p\_e \to r\_v$ (when $v \in C$) or $p\_e \to r\_u$ (when $u \in C$). Note that in both cases, the character that $p\_e$ needs to be converted into is in the cycle of substitutions, meaning that the above instructions successfully convert the choice gadgets as well.

This shows that if the answer to the vertex cover instance is "yes", then the edit distance between $A$ and $B$ is at most $k'$.

What about the reverse direction?

Let's say there is a way to edit $A$ into $B$ using at most cost $k'$. Suppose we have the solution with the least cost. When we analyzed the choice gadget, we saw that there is always an efficient (least cost) solution involving one deletion in that choice gadget, specifically deleting either $x\_1$ or $x\_2$ in the gadget. Thus we can assume WLOG that our least-cost solution has no insertions and exactly one deletion in each choice gadget and that the deletion is one of the two intended deletions. That's an insertion/deletion cost of $m$ in the choice gadgets alone. Therefore, the substitution cost must be at most $k' - m = 3m + k$.

Due to the alignment gadgets we know that the choice gadgets must be solved entirely by substitution after the one deletion in that gadget. Therefore, for each edge $e = (u,v)$, we either have a substitution of $x\_1p\_e \to r\_ur\_v$ or $p\_ex\_2 \to r\_ur\_v$. Define a set of vertices $C$ such that $v \in C$ if and only if there is a substitution $p\_e \to r\_v$ that needs to happen in some edge gadget. By the above, we see that $C$ must be a vertex cover (since each edge gadget contributes one of the endpoints of the edge to $C$).

We also know from the forced substitution gadgets that $p\_e \to q\_e$ and $q\_e \to p\_e$ are forced substitutions.

Let $A'$ be the state of the string after the insertion/deletion step and before the substitution step. At this point we will use the key fact from the first section to determine what the substitution cost must be. We know that there is a directed graph $T\_{A'\to B}$ whose edges are the substitutions that are required to convert $A'$ into $B$. We know from the above that this graph includes the following edges:

* $(p\_e, q\_e)$ and $(q\_e, p\_e)$ for every edge $e$ in $G$
* Either $(x\_1, r\_u)$ and $(p\_e, r\_v)$, or $(x\_2, r\_v)$ and $(p\_e, r\_u)$ for each edge $e = (u,v)$ (where the $x\_1$ and $x\_2$ vertices are unique per edge $e$)

According to the key fact from the previous section, the substitution cost is equal to the number of vertices in this graph minus the number of acyclic weakly connected components. This value can never decrease if we add more vertices or edges, so computing this value for only those edges listed above is a lower bound on the substitution cost of our edit solution.

There are exactly $3m+n$ vertices listed above, where $n$ is the number of vertices in $G$ (one $p\_e$ vertex per edge of $G$, one $q\_e$ vertex per edge of $G$, one $x\_1$ or $x\_2$ per choice gadget--of which there are $m$, and one $r\_v$ per vertex of $G$). What about the number of acyclic weakly connected components? Due to the cycle $p\_e, q\_e, p\_e$, the connected components of vertices $p\_e$ are never acyclic. As for each $r\_v$, it either connects to some $p\_e$, in the case that $v \in C$, or it does not connect to any $p\_e$ if $v \not\in C$. In the former case, this vertex is not in an acyclic weakly connected component. In the latter case, the entire weakly connected component of $r\_v$ is that vertex with some number of $x\_1$ or $x\_2$ vertices neighboring it. That is acyclic. As for the $x\_1$ or $x\_2$ vertices, each one neighbors an $r\_v$ vertex, and its weakly connected component has therefore already been addressed one way or the other above. Thus, we see that each acyclic weakly connected component contains exactly one $r\_v$ vertex and furthermore one where $v \not\in C$. Thus, the number acyclic weakly connected components is equal to the number of vertices $v$ not in $C$. This equals $n - |C|$.

The substitution cost therefore has a lower bound of $(3m+n) - (n-|C|) = 3m+|C|$. But we saw before that the substitution cost must be at most $k' - m = 3m + k$. Therefore, we see that it must be the case that $|C| \le k$. Then $C$ is a vertex cover of size at most $k$, proving that the answer to the vertex cover instance is "yes".

We have shown via the two directions that $G$ has a vertex cover of size at most $k$ if and only if $A$ and $B$ have an edit distance of at most $k'$. This proves that the reduction is correct. Since we previously noted that it runs in polynomial time, this concludes the proof that computing edit distance (as you defined it) is NP-hard.

> **Comments:**
> **username_0**: Very nice! Thank you. At least my question wasn't too trivial :)  

---

