Overview
The graph edit distance (GED) problem is generally NP-hard, incorporating several other known NP-hard problems as special cases. This study examines the computational complexity of GED, focusing on its relationship with specific graph classes and the chosen edit cost functions. The investigation leverages existing polynomial-time reductions from problems such as subgraph isomorphism and maximum common induced subgraph to GED. A core aspect of this research involves making explicit the implications of known distinctions between NP-hard and polynomial-time solvable instances of these classical problems for the complexity of GED.
Research Context
Graph edit distance serves as a flexible similarity measure between graphs, quantifying the minimum cost sequence of graph edit operations (insertions, deletions, substitutions of vertices and edges) required to transform one graph into another. Its broad applicability has led to its generalization of other complex graph problems. The inherent NP-hardness of GED stems from its ability to subsume problems like subgraph isomorphism and maximum common induced subgraph. A key challenge in understanding GED's complexity lies in discerning how different graph classes and variations in the edit cost function influence its computational tractability. Prior literature includes polynomial-time reductions that link these classical problems to GED, providing a foundation for exploring the complexity landscape.
Approach
The methodology involved revisiting polynomial-time reductions established in existing literature. These reductions link problems such as subgraph isomorphism and maximum common induced subgraph to the graph edit distance. The study then analyzed the implications of known sharp distinctions between NP-hard and polynomial-time solvable cases for these classical problems, applying them to the complexity of the graph edit distance. A further step involved establishing a graph-class-preserving correspondence between the maximum common edge subgraph (MCES) problem and the graph edit distance. This correspondence was investigated under a specific cost function and considered both labeled and unlabeled graphs.
Findings
- The graph edit distance generalizes several NP-hard problems and is itself NP-hard.
- The computational complexity of graph edit distance is influenced by specific graph classes and the chosen edit cost functions.
- Polynomial-time reductions from literature, which reduce subgraph isomorphism and maximum common induced subgraph to graph edit distance, can be used to delineate complexity for GED.
- A graph-class-preserving correspondence exists between the maximum common edge subgraph (MCES) problem and the graph edit distance when a specific cost function is employed. This correspondence holds for both labeled and unlabeled graphs.
- In the context of unlabeled graphs, the maximum common edge subgraph problem is polynomial-time solvable when one of the graphs is a path and the other is a tree.
- Conversely, for labeled graphs, both the maximum common edge subgraph problem and the graph edit distance remain NP-hard, even when both graphs under consideration are paths.