Say I generalize the language which consists of pairs of isomorphic graphs to take the following form:

$GI(f) = \{ (G, H) \mid \exists \psi : V_G \rightarrow V_H, Pr_{a, b \in V_G} ((a, b) \in E_G \Longleftrightarrow (\psi(a), \psi(b)) \in E_H) \geq f\}$

Is there any work on this language? The obvious question is whether there exists $f$ such that $GI(f) \in P$. The funny counterpart to this language is

$IG(f) = \{ (G, H) \mid \forall \psi : V_G \rightarrow V_H, Pr_{a, b \in V_g}((a, b) \in E_G \Longleftrightarrow (\psi(a), \psi(b)) \in E_H) \leq f \}$

Just wanted to hear the thoughts of anyone who wanted to have a go at constructing algorithms for different constant values of $f$ or perhaps for $f$ as a function of the size of the vertex sets or something.


This is the decision version of what is sometimes called "Approximate Graph Isomorphism." While I won't say it's been studied a lot, it has been studied. See, for example:

[AKKV] Arvind, Kobler, Kuhnert, & Vasudev. Approximate graph isomorphism. MFCS '12. (freely available ECCC version)

In particular, [AKKV] show that one can approximate the maximum (over bijections $V(G) \to V(H)$) of the number of matches to any constant factor in $n^{O(\log n)}$ time, but that any constant-factor approximation to the minimum number of mismatches is $\mathsf{NP}$-hard.

[GRW] Grohe, Rattan, & Woeginger. Graph similarity and approximate isomorphism. arXiv:1802.08509 [cs.DS]

[GRW] show that computing the minimum number of mismatches is $\mathsf{NP}$-hard even on trees. They also show that in the weighted case, it is $\mathsf{NP}$-hard if either weighted adjacency matrix has unbounded rank or negative eigenvalues (so the easy cases are a subset of PSD matrices of bounded rank).

This problem is also sometimes called "graph similarity" (which I consider a much more general term) or "graph matching" (which you'll have a hard time Googling because you'll get a lot of stuff about matchings), and has apparentely been studied more in the ML and data mining literature.


I wasn't able to figure out whether $\mathrm{GI}(1/2)\in\mathsf P$, but here is a weaker result: The languages $\mathrm{GI}(1/2)$ and $\mathrm{GI}$ are not $\mathsf P$-inseparable.

Proof: It suffices to show the first reverse inclusion in $$\mathrm{GI}(1/2)\supseteq\{(G,H): |V_G|=|V_H|, |E_G|=|E_H|\} \supseteq \mathrm{GI}(1)=\mathrm{GI}.$$ Let $p$ be the probability that $(a,b)\in E_G$ for uniformly random $a$, $b$.

Let $\Psi:V_G\to V_H$ be a uniformly random function and also let $a$ and $b$ be selected randomly, with $\Psi$, $a$, $b$ mutually independent. Then the two events $$\mathscr U = \{(a,b)\in E_G\}\text{,}\quad \mathscr V=\{(\Psi(a),\Psi(b))\in E_H\}$$ are independent. Therefore $$\Pr_{\Psi,a,b}(\mathscr U\leftrightarrow\mathscr V)=p^2+(1-p)^2\ge 1/2.$$

So by Fubini's Theorem there is some $\psi$ such that $\Pr_{a,b}(\mathscr U\leftrightarrow\mathscr V\mid \Psi=\psi)\ge 1/2.\qquad\Box$

  • $\begingroup$ I'm not sure what P-inseparability is nor was I able to find the definition online. Could you help me out? $\endgroup$ – Samuel Schlesinger Oct 8 '17 at 23:10
  • $\begingroup$ Oh sorry... I meant $A\subseteq B$ are $P$-inseparable if there is no problem $C$ in $P$ with $A\subseteq C\subseteq B$. $\endgroup$ – Bjørn Kjos-Hanssen Oct 8 '17 at 23:22
  • $\begingroup$ Original definition is: disjoint sets $A$ and $B$ are $P$-inseparable if there is no $C$ in $P$ with $A\subseteq C$ and $C$, $B$ still disjoint. $\endgroup$ – Bjørn Kjos-Hanssen Oct 8 '17 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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