How to transform a vertex-labeled graph to another while keeping its connectivity and maximum degree during the transformation.

Question

There are two connected, vertex-labeled, undirected graph $G$ and $G^*$, where

1. $V(G)$ = $V(G^*)$, all nodes are labeled;
2. $\triangle (G) \leq k$, $\triangle (G^*) \leq k$, where $k>2$;

I want to move/add/delete the edges of $G$ to transform it to $G^*$, while all the interim graphs must be connected and its maximum degree must not exceed $k$.

An example is shown in the following figure.

It is easy to transform such a graph (denoted as $G$) to a ring (denoted as $R(G)$ via deleting/adding edges, and such an transformation is always reversible.

So a feasible solution (no optimal) is: $G$ --> $R(G)$ --> $R(G^*)$ --> $G^*$.

How to find more optimal solutions?

Answer 1

Maintaining connectedness and the maximal degree makes this problem harder than the problem of computing graph edit distance. (Excluding vertex insertion/deletion is not significant.) Merely computing the graph edit distance between two graphs is NP-hard.

Papers:

• Comparing Stars: On Approximating Graph Edit Distance

• Approximate graph edit distance computation by means of bipartite graph matching

• A survey of graph edit distance