# Fast algorithm for Graph Edit Distance to vertex-labeled Path Graph

Let $$G$$ be a vertex-labeled directed graph with unique labels $$L$$. Let $$G_P$$ be a path graph with the same vertex labels and the same number of vertices as $$G$$.

I know that in the general case computing the Graph Edit Distance is NP-hard (if approximations are excluded) and APX-hard to approximate.

I'm interested in a subset of the problem:

Is there a general algorithm for quickly computing the Graph Edit Distance from any $$G$$ to any $$G_P$$, restricted to only adding and removing edges?

Let, for example, $$G=(\{a,b,c\}, \{(a,b), (b,c), (c,a)\})$$:

Then the graph edit distance, excluding vertex addition/deletion, to the path directed graph $$G_P=(\{a,b,c\}, \{(a,b), (b,c)\})$$ is 1.

It feels to me like this is a case that's restricted enough that there should be an efficient algorithm for computing the distance, but I might be mistaken.

Furthermore, for a given directed vertex-labeled graph, is there a known algorithm for finding the set of labeled path graphs with the minimal graph-edit distance to the original graph?

So far, for both questions, I haven't been able to find an answer (google scholar gives only semi-related answers to "graph edit distance to linear graph" and "graph edit distance to path graph".

Context for why I'm asking the question, probably not relevant to the answer.

The edit cost can be expressed as $$|E| + |P| - 2 |E \cap P|$$ where $$(V, E)$$ is the source graph and $$P$$ is the target path. By setting cost $$0$$ on edges and cost $$1$$ to non-edges, the cost of a tour is equal to the edit cost of the path plus some constant.
0-1 TSP is NP-hard but solvable in $$O(2^n n^2)$$ time by dynamic programming.