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

Question

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.

Answer 1

If both graphs have the same unique labels, there is a unique minimal way to edit edges: remove edges missing in the target, and add edges missing in the source. This problem is solvable in a linear time.

For finding the minimal-distance path graph (permutation), this is equivalent to the 0-1 TSP (the traveling salesman problem with edge cost 0 or 1):

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.