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.


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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