8
$\begingroup$

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

$\endgroup$
12
  • 1
    $\begingroup$ Can you find a case where the sequence of operations found with the regular Levenshtein distance is not also optimal for this problem? $\endgroup$
    – causative
    Nov 22 '20 at 6:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Nov 22 '20 at 6:34
  • $\begingroup$ @D.W. I should have said, we should assume the alphabet size can be as large as n. $\endgroup$
    – Anush
    Nov 22 '20 at 7:06
  • $\begingroup$ My intuition says that it can be done in polynomial time, but I am too lazy to think of a way. $\endgroup$
    – user21820
    Nov 22 '20 at 7:40
  • 1
    $\begingroup$ Yep. I posted my answer :) $\endgroup$ Dec 18 '20 at 11:07
4
+50
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Very nice! Thank you. At least my question wasn't too trivial :) $\endgroup$
    – Anush
    Dec 18 '20 at 11:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.