pith. sign in

arxiv: 2309.03810 · v2 · submitted 2023-09-07 · 💻 cs.DM · cs.CC

Three Hardness Results for Graph Similarity Problems

He Sun , Danny Vagnozzi This is my paper

Pith reviewed 2026-05-24 06:47 UTC · model grok-4.3

classification 💻 cs.DM cs.CC
keywords graph similarityedit distanceNP-hardnessgraph isomorphism1-planar graphsstrongly regular graphsoperator normsmismatch norms
0
0 comments X

The pith

Optimal graph edit distance is NP-hard to compute even when input graphs have exactly the same number of edges.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes NP-hardness for computing the exact value of the edit-distance similarity measure δ_E on pairs of graphs that share an identical edge count. It further shows that the two ℓ_p-norm based similarity measures δ_p and δ_|p| remain NP-hard to compute on the narrower class of 1-planar graphs that also share the same degree sequence and have bounded maximum degree. These restrictions matter because the measures were examined as possible polynomial-time proxies for deciding graph isomorphism; hardness of exact computation blocks that route on the restricted inputs. The proofs strengthen earlier results by enforcing the equal-edge and 1-planarity conditions. Additional inequalities are derived for the same measures restricted to strongly regular graphs.

Core claim

Computing an optimal value of δ_E is NP-hard on pairs of graphs with the same number of edges. In addition, we show that computing optimal values of δ_p and δ_|p| is NP-hard even on pairs of 1-planar graphs with the same degree sequence and bounded degree. These two results improve on previous known ones, which did not examine the restricted case where the pairs of graphs are required to have the same number of edges. Finally, we study similarity problems on strongly regular graphs and prove some near optimal inequalities with interesting consequences on the computational complexity of graph and group isomorphism.

What carries the argument

Mismatch norms that induce the edit distance δ_E together with the ℓ_p-operator-norm distances δ_p and δ_|p|.

If this is right

  • Exact computation of δ_E cannot be performed in polynomial time on equal-edge graph pairs unless P equals NP.
  • Exact computation of δ_p and δ_|p| cannot be performed in polynomial time on the stated 1-planar pairs unless P equals NP.
  • These similarity measures cannot yield polynomial-time approximation algorithms for graph isomorphism on the restricted graph classes.
  • Near-optimal inequalities constrain the possible similarity values between non-isomorphic strongly regular graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Any computational pipeline that relies on exact values of these distances must incorporate exponential-time subroutines or accept approximation error on the restricted inputs.
  • The 1-planar hardness may interact with existing polynomial-time isomorphism algorithms for planar graphs to produce new conditional lower bounds.
  • The reduction technique could be tested for preservation of other structural properties such as bounded treewidth or fixed genus.

Load-bearing premise

The NP-hardness reductions can be constructed so that the produced graph pairs satisfy equal edge count (for δ_E) or 1-planarity plus identical degree sequences and bounded degree (for δ_p and δ_|p|) while preserving a positive optimality gap.

What would settle it

A polynomial-time algorithm that returns the exact optimal value of δ_E for every pair of graphs having the same number of edges.

Figures

Figures reproduced from arXiv: 2309.03810 by Danny Vagnozzi, He Sun.

Figure 1
Figure 1. Figure 1: Construction of Gπ − H based on G, H, and π mapping ui 7→ vi . Here, the edges (v1, v2) and (v3, v4) are positive and negative for π respectively. obtain the graph Gπ . In the spirit of the above, we refer to the elements of E(Gπ )∩ E(H) as being neutral for π. Note that V (H) together with the neutral and positive edges of Gπ − H form the graph Gπ , and V (H) together with the neutral and negative edges o… view at source ↗
Figure 2
Figure 2. Figure 2: The left is a 3-regular graph G, and the right is our constructed G [q]. The green circles indicate the auxiliary (q + 1)-cliques. Construction of Dn,q. For any even value of n and q ∈ N, we construct the graph Dn,q as follows: • The vertex set of Dn,q is the same as that of Cn[q], where Cn is an n-cycle; • Let M be a matching of Cn. The edge set of Dn,q is defined as E(Dn,q) , E(Cn[q])[nu [1], v[1] | (u… view at source ↗
Figure 3
Figure 3. Figure 3: The graph D6,q obtained by adding the blue edges to C6 [q]. 7 [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The left figure illustrates the construction of [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The left figure is used in the proof of Lemma 4.5 for ev [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
read the original abstract

Notions of graph similarity provide alternative perspective on the graph isomorphism problem and vice-versa. In this paper, we consider measures of similarity arising from mismatch norms as studied in Gervens and Grohe: the edit distance $\delta_{\mathcal{E}}$, and the metrics arising from $\ell_p$-operator norms, which we denote by $\delta_p$ and $\delta_{|p|}$. We address the following question: can these measures of similarity be used to design polynomial-time approximation algorithms for graph isomorphism? We show that computing an optimal value of $\delta_{\mathcal{E}}$ is \NP-hard on pairs of graphs with the same number of edges. In addition, we show that computing optimal values of $\delta_p$ and $\delta_{|p|}$ is \NP-hard even on pairs of $1$-planar graphs with the same degree sequence and bounded degree. These two results improve on previous known ones, which did not examine the restricted case where the pairs of graphs are required to have the same number of edges. Finally, we study similarity problems on strongly regular graphs and prove some near optimal inequalities with interesting consequences on the computational complexity of graph and group isomorphism.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper establishes three NP-hardness results for computing optimal values of graph similarity measures based on mismatch norms: δ_E (edit distance) is NP-hard even for pairs of graphs with identical numbers of edges; δ_p and δ_|p| (from ℓ_p-operator norms) are NP-hard even for pairs of 1-planar graphs with identical degree sequences and bounded maximum degree. It additionally derives near-optimal inequalities relating these distances on strongly regular graphs and discusses consequences for the complexity of graph and group isomorphism.

Significance. If the reductions are valid, the results meaningfully strengthen prior hardness statements by enforcing natural restrictions (equal edge cardinality; 1-planarity plus degree-sequence equality) that are relevant when considering whether these distances can yield approximation algorithms for graph isomorphism. The strongly-regular-graph inequalities supply concrete, falsifiable bounds that may be useful for algorithmic or complexity-theoretic follow-up work.

major comments (2)
  1. [Sections containing the reductions for Theorems on δ_E, δ_p and δ_|p|] The central reductions (for δ_E and for δ_p/δ_|p|) must produce output instances that exactly satisfy the stated restrictions while retaining a positive optimality gap. For the δ_E result this requires that every auxiliary construction adds precisely the same number of edges to both graphs; for the δ_p/δ_|p| result the outputs must remain 1-planar, bounded-degree, and degree-sequence identical. Any gadget that inadvertently creates a low-cost mapping on yes-instances or inflates the distance on no-instances would collapse the gap and invalidate the claim.
  2. [Proofs of the 1-planar bounded-degree results] It is not immediate from the high-level description whether the 1-planarity and degree-sequence constraints are enforced by local, gap-preserving modifications or by global adjustments that could introduce new isomorphisms or low-norm mappings. A concrete verification that the chosen gadgets (vertex/edge additions, subdivisions, etc.) preserve both the structural invariants and the distance gap is required.
minor comments (2)
  1. Notation for the three distances (δ_E, δ_p, δ_|p|) should be introduced once with explicit reference to the underlying mismatch-norm definitions from Gervens and Grohe.
  2. The abstract states that the new results 'improve on previous known ones'; a brief comparison table or paragraph citing the exact prior statements being strengthened would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for explicit verification that our reductions preserve the stated restrictions and the optimality gap. We address each major comment below and will revise the manuscript accordingly to include more detailed gadget analyses.

read point-by-point responses

  1. Referee: [Sections containing the reductions for Theorems on δ_E, δ_p and δ_|p|] The central reductions (for δ_E and for δ_p/δ_|p|) must produce output instances that exactly satisfy the stated restrictions while retaining a positive optimality gap. For the δ_E result this requires that every auxiliary construction adds precisely the same number of edges to both graphs; for the δ_p/δ_|p| result the outputs must remain 1-planar, bounded-degree, and degree-sequence identical. Any gadget that inadvertently creates a low-cost mapping on yes-instances or inflates the distance on no-instances would collapse the gap and invalidate the claim.

    Authors: The constructions in Sections 3 and 4 are designed to satisfy the restrictions exactly. For δ_E, the reduction augments both graphs with identical numbers of pendant edges and isolated vertices (added symmetrically), preserving equal edge cardinality while the mismatch cost on the core remains unchanged. For δ_p and δ_|p|, the gadgets consist of local 1-planar subdivisions and degree-regularizing attachments applied identically to both graphs; these maintain 1-planarity, maximum degree 6, and identical degree sequences. The gap is retained because any low-cost mapping on yes-instances must align the gadgets perfectly (adding zero extra cost) and the no-instances incur a fixed positive penalty independent of the gadgets. We agree the current text is high-level and will add an expanded subsection with explicit case analysis of each gadget type. revision: yes

  2. Referee: [Proofs of the 1-planar bounded-degree results] It is not immediate from the high-level description whether the 1-planarity and degree-sequence constraints are enforced by local, gap-preserving modifications or by global adjustments that could introduce new isomorphisms or low-norm mappings. A concrete verification that the chosen gadgets (vertex/edge additions, subdivisions, etc.) preserve both the structural invariants and the distance gap is required.

    Authors: All modifications are strictly local and symmetric. Vertex subdivisions and edge additions are performed identically on corresponding parts of both input graphs, ensuring 1-planarity is inherited from the base 1-planar graphs and degree sequences remain equal by construction. These local changes do not create new low-norm mappings on yes-instances because the gadgets are rigid (e.g., using asymmetric attachments that force unique optimal alignments). On no-instances the added cost is constant and positive. No global adjustments are used. We will include concrete gadget diagrams, formal proofs of invariance, and gap calculations in the revised version to make this verification immediate. revision: yes

Circularity Check

0 steps flagged

No circularity: hardness via standard reductions from known NP-complete problems

full rationale

The paper proves NP-hardness of computing optimal δ_E (on equal-edge graphs), δ_p and δ_|p| (on 1-planar bounded-degree same-degree-sequence graphs) by polynomial-time reductions. These are self-contained complexity arguments that do not define any quantity in terms of itself, do not rename fitted parameters as predictions, and do not rely on load-bearing self-citations or imported uniqueness theorems. The abstract and claimed results contain no equations or steps that reduce by construction to their own inputs; the load-bearing step is the existence of gap-preserving gadgets satisfying the stated restrictions, which is an external combinatorial claim rather than a definitional loop.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on the standard definition of NP-hardness via polynomial-time reductions and on the definitions of the similarity measures δ_E, δ_p, and δ_|p|; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)
  • standard math NP-hardness is established by polynomial-time many-one reductions from a known NP-hard problem.
    Invoked implicitly when stating that computing the optimal values is NP-hard.
  • domain assumption Graph properties such as 1-planarity, bounded degree, and equal degree sequences are preserved under the reductions.
    Required for the strengthened hardness claims on the restricted graph classes.

pith-pipeline@v0.9.0 · 5729 in / 1369 out tokens · 19422 ms · 2026-05-24T06:47:42.393415+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages · 1 internal anchor

  1. [1]

    A. A. Albert. Quasigroups. I. Transactions of the American Mathematical Society , 54(3):507– 519, 1943

    work page 1943

  2. [2]

    Approximate graph isomorphism

    Vikraman Arvind, Johannes K¨ obler, Sebastian Kuhnert, and Yadu Vasudev. Approximate graph isomorphism. In Mathematical Foundations of Computer Science 2012 , pages 100–111, 2012

    work page 2012

  3. [3]

    Graph Isomorphism in Quasipolynomial Time

    L´ aszl´ o Babai. Graph isomorphism in quasipolynomial time. ArXiv, abs/1512.03547, 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  4. [4]

    The geometry of diagonal groups

    R Bailey, Peter Cameron, Cheryl Praeger, and Csaba Schne ider. The geometry of diagonal groups. Transactions of the American Mathematical Society , 375(08):5259–5311, 2022

    work page 2022

  5. [5]

    R. A. Bailey. Design of comparative experiments , volume 25 of Cambridge Series in Statistical and Probabilistic Mathematics . Cambridge University Press, Cambridge, 2008

    work page 2008

  6. [6]

    Cameron, and Taoyang Wu

    Christoph Buchheim, Peter J. Cameron, and Taoyang Wu. On the subgroup distance problem. Discrete Mathematics, 309(4):962–968, 2009

    work page 2009

  7. [7]

    Peter J. Cameron. Strongly regular graphs. Lecture Notes, 2003

    work page 2003

  8. [8]

    Colbourn, Torleiv Kløve, and Alan C

    Charles J. Colbourn, Torleiv Kløve, and Alan C. H. Ling. P ermutation arrays for powerline communication and mutually orthogonal Latin squares. IEEE Transactions on Information Theory, 50:1289–1291, 2004

    work page 2004

  9. [9]

    Thirty years of graph matching in pattern recognition

    Donatello Conte, Pasquale Foggia, Carlo Sansone, and Ma rio Vento. Thirty years of graph matching in pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence, 18:265–298, 2004

    work page 2004

  10. [10]

    M. Dehn. ¨Uber unendliche diskontinuierliche gruppen. Mathematische Annalen , 71:116–144, 1911

    work page 1911

  11. [11]

    On a problem of L

    J D´ enes. On a problem of L. Fuchs. Acta Sci. Math.(Szeged) , 23:237–241, 1962

    work page 1962

  12. [12]

    Pr aeger

    Diane Donovan, Sheila Oates-Williams, and Cheryl E. Pr aeger. On the distance between distinct group Latin squares. Journal of Combinatorial Designs , 5(4):235–248, 1997. 22

    work page 1997

  13. [13]

    How far apart can the group multiplicati on tables be? European Journal of Combinatorics, 13(5):335–343, 1992

    Aleˇ s Dr´ apal. How far apart can the group multiplicati on tables be? European Journal of Combinatorics, 13(5):335–343, 1992

    work page 1992

  14. [14]

    Fifty years of graph matching, network alignment and network comparison

    Frank Emmert-Streib, Matthias Dehmer, and Yongtang Sh i. Fifty years of graph matching, network alignment and network comparison. Information Sciences , 346-347:180–197, 2016

    work page 2016

  15. [15]

    Graph matching and learning in pattern recognition in the last 10 years

    Pasquale Foggia, Gennaro Percannella, and Mario Vento . Graph matching and learning in pattern recognition in the last 10 years. International Journal of Pattern Recognition and Artificial Intelligence , 28, 2014

    work page 2014

  16. [16]

    Graph similarity based o n matrix norms

    Timo Gervens and Martin Grohe. Graph similarity based o n matrix norms. In 47th Inter- national Symposium on Mathematical Foundations of Computer Science (MFCS’22) , pages 52:1–52:15, 2022

    work page 2022

  17. [17]

    Woeginger

    Martin Grohe, Gaurav Rattan, and Gerhard J. Woeginger. Graph similarity and approximate isomorphism. In International Symposium on Mathematical Foundations of Comp uter Science, 2018

    work page 2018

  18. [18]

    Spectrally Robust Graph Isomorphism

    Alexandra Kolla, Ioannis Koutis, Vivek Madan, and Ali K emal Sinop. Spectrally Robust Graph Isomorphism. In 45th International Colloquium on Automata, Languages, and Pr ogramming (ICALP’18), pages 84:1–84:13, 2018

    work page 2018

  19. [19]

    N P-completeness of the Hamiltonian cycle problem for bipartite graphs

    Akiyama Takanori, Nishizeki Takao, and Saito Nobuji. N P-completeness of the Hamiltonian cycle problem for bipartite graphs. Journal of Information Processing , 3(2):73–76, 08 1980

    work page 1980

  20. [20]

    S. Umeyama. An eigendecomposition approach to weighte d graph matching problems. IEEE Transactions on Pattern Analysis and Machine Intelligence , 10(5):695–703, 1988. A Proposition 5.3 is tight up to a small constant term The combinatorics in the proof of Proposition 5.3 is rather c rude, so one might expect that a better bound are attainable for certain ...

    work page 1988

  21. [21]

    a1 = b1, in which case we call the edge between ( a1, a 2) and ( b1, b 2) a row edge

    work page

  22. [22]

    a2 = b2, in which case we call to the edge between ( a1, a 2) and ( b1, b 2) a column edge. 23

    work page

  23. [23]

    In this case, we call the edge between ( a1, a 2) and ( b1, b 2) an entry edge

    There is some c ∈ A for which c is the ( a1, a 2)-entry as well as the ( b1, b 2)-entry of the Latin square Λ. In this case, we call the edge between ( a1, a 2) and ( b1, b 2) an entry edge . Note that from the definition of a Latin square, each edge sati sfies exactly one of the above condi- tions. For simplicity, we consider Z4 and ( Z2)2 as groups over t...

    work page

  24. [24]

    In particular, all odd vertices are twinned with their image under the mapping (gi, h j) ↦→ (gis, h js)

    The vertices (gi, h j ) and (gis, h js) have the same parity. In particular, all odd vertices are twinned with their image under the mapping (gi, h j) ↦→ (gis, h js)

    work page

  25. [25]

    An even vertex (gi, h j) is twinned with (gis, h js) if and only if i and j are both even

    work page

  26. [26]

    Then gi ·hj = g′ k ·h′ l if and only if gis ·hjs = g′ ks ·h′ ls

    Consider the even vertices (gi, h j) and (g′ k, h ′ l) where i, j, k, l are odd. Then gi ·hj = g′ k ·h′ l if and only if gis ·hjs = g′ ks ·h′ ls. Proof. Note that k the map (gi, h j ) ↦→ (gis, h js) preserves the Γ component of the vertices, so the three state ments above can be verified directly from the Cayley tables in Table 1. Proof of Proposition A.1....

    work page