Let us denote the original graph $G_O$ and the target graph $G_T$.
I am wondering if there exists an algorithm that uses the minimum number of edge deletions and additions to make $G_0$ isomorphic to $G_T$.
I have been searching for a bit and found graph matching as the closest thing, but it only checks if two graphs are isomorphic. Can anyone give me some directions or references? Thank you
This is equivalent to finding the maximum common subgraph.
A solution that removes $b$ edges and adds $c$ edges means that $G_0$ and $G_T$ both have a subgraph isomorphic to the same $G_\text{mid}$ with $|E(G_0)| - b = |E(G_T)| - c$ edges (the graph obtained after removing but before adding edges). Conversely, a common subgraph $G_\text{mid}$ means there is a solution removing $|E(G_0)| - |E(G_\text{mid})|$ edges and then adding $|E(G_T)| - |E(G_\text{mid})|$ edges, for a total of $|E(G_0)| + |E(G_T)| - 2|E(G_\text{mid})|$. Since $|E(G_0)| + |E(G_T)|$ is fixed, minimizing the number of additions and deletions is the same as maximizing $|E(G_\text{mid})|$.
Wikipedia calls it Maximum common edge subgraph for disambiguation, but most references just say maximum common subgraph without edge.
Note that the problem is NP-hard, because even finding a clique of given size is NP-hard (the clique [decision] problem). A graph $G$ contains $K_n$ iff you can add/remove $|E(G)|-|E(K_n)|$ edges to $K_n$ to obtain a graph isomorphic to $G$.