{"id":"arxiv/2608.17990","url":"https://arxiv.org/abs/2608.17990","tags":["cs.DS","cs.CC","math.CO","math.MG"],"score":0,"title":"Cluster-Graph Edit Distance: Optimal Explicit Embeddings, Metric Proxies, and Complexity","domain":"cs.DS","source":"arxiv","authors":["JiYe Liu","Wenkai Wang","Qiang Tian","Wenjun Wang"],"reviews":0,"subject":"cs.DS","summary":"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^*(λ,μ)=\\min_{σ\\in S_n}|E(G_λ)\\triangleσE(G_μ)|$ makes that set a metric space. Its geometry and its complexity both issue from one identity: $q^*$ is an affine function of the maximum of $\\lVert X\\rVert_F^2$ over the contingency tables with margins $λ$ and $μ$. Our main result is an explicit optimal embedding. The weighted dyadic sums of the Ferrers staircase, taken at the critical exponent $\\frac14$, give a map $F_n$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-18","reactions":{}}