Metraipolis › archive › dc_daca3cc06ba6
A Separator-based Algorithm for the Graph Edit Distance Problem — arXiv:2608.04583
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.04583
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T11:58:21.311Z
- SHA-256 of the archived text
c86f527afff5bd92747412ff215577b05955147534bdd65337b2a033e8df0a75- Stable URL of this page
https://metraipolis.com/documento/dc_daca3cc06ba6
How to cite
A Separator-based Algorithm for the Graph Edit Distance Problem — arXiv:2608.04583 — arXiv (en), https://arxiv.org/abs/2608.04583 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_daca3cc06ba6 (Metraipolis archive dc_daca3cc06ba6, sha256 c86f527afff5bd92747412ff215577b05955147534bdd65337b2a033e8df0a75)
BibTeX
@misc{dcdaca3cc06ba6,
title = {A Separator-based Algorithm for the Graph Edit Distance Problem — arXiv:2608.04583},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.04583},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_daca3cc06ba6; sha256 c86f527afff5bd92747412ff215577b05955147534bdd65337b2a033e8df0a75},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.04583. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The Graph Edit Distance (GED) is a widely used graph similarity measure asking for the minimum cost of a sequence of edits transforming one (labeled) graph into another. The considered edit operations are deletion, insertion, and relabeling of nodes and edges. Special cases include the Graph Isomorphism problem, as well as many other graph problems that ask for the existence or minimum cost of a certain substructure, like the Traveling Salesman or Maximum Clique problem. We present a novel exponential time algorithm to compute the exact GED and a corresponding edit sequence in $O^*(4 + \varepsilon)^n$ time and polynomial space, provided one of the two graphs admits strictly sublinear balanced separators. In particular, the claimed runtime holds if one of the graphs is $K_h$-minor free (e.g., planar), or has bounded treewidth, which is the case for many real-world applications (e.g., all instances in GEDLIB). This substantially improves the best known worst-case running time bounds of $O^*(n!)$ for these graph classes. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-06 in cs.DS). Categorie arXiv: Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2608.04583 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-31T11:47:39.822Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).