Cluster-Graph Edit Distance: Optimal Explicit Embeddings, Metric Proxies, and Complexity

Abstract

The cluster graphs on $n$ vertices, the disjoint unions of complete graphs, have the integer partitions of $n$ as their isomorphism classes, and the quotient edit distance $q^{\ast }(\lambda ,\mu )={\min }_{\sigma \in S_n}|E(G_{\lambda })△\sigma E(G_{\mu })|$ makes that set a metric space. Its geometry and its complexity both issue from one identity: $q^{\ast }$ is an affine function of the maximum of $\Vert X{\Vert }_F^2$ over the contingency tables with margins $\lambda$ and $\mu$. Our main result is an explicit optimal embedding. The weighted dyadic sums of the Ferrers staircase, taken at the critical exponent $\frac{1}{4}$, give a map $F_n$ into ${\ell }_2^{<4n}$ that acts on a single partition and is computable in $O(n)$ time, and its distortion is $\Theta (n^{1/4})$. That order is optimal, since $c_2({\mathcal{K}}_n)=\Theta (n^{1/4})$: the lower half follows from a $\Theta (\sqrt{n})$-dimensional Hamming cube of partitions and Enflo's theorem, so the determination needs no other external input. The analytic core is a scale-free inverse inequality for every integer sequence with $v(1)=v(N+1)=0$ and $v(s)-v(s+1)\in s\mathbb{Z}$: its critical dyadic energy is at least $\Vert v{\Vert }_1^2/(63504\sqrt{\mathrm{TV}(v)})$. Combinatorially the same identity yields two explicit ${\ell }_1$ models, the vertex-mass metric on sorted degree sequences with $\frac{1}{2}{\delta }_1\le q^{\ast }<\frac{3}{2}{\delta }_1$ and the block-energy metric with $q^{\ast }\le B\le 2q^{\ast }-1$, both constants optimal; hence $c_1({\mathcal{K}}_n)\le 2$, and an $O(n\log n)$-time algorithm returns an alignment of cost below $2q^{\ast }$ carrying the certificate $q^{\ast }\in [\lceil (B+1)/2\rceil ,B]$. Computationally, deciding $q^{\ast }(\lambda ,\mu )\le Q$ is strongly NP-complete and admits no FPTAS, while the farthest alignment is polynomial-time solvable. The best constant in the inverse inequality remains open; an exactly solvable chirp family caps it at $\frac{2}{3}$.

49 pages, 6 figures. v2: the critical inverse-energy conjecture of v1 is now proved, as a scale-free inverse theorem on the full cone of closed quantized integer sequences (Theorem 6.2)