Search papers, labs, and topics across Lattice.
This paper introduces $\Delta$-DRESS, a single-level vertex deletion method within the DRESS framework, for generating unique graph fingerprints. They empirically demonstrate that $\Delta$-DRESS achieves 100% within-family separation across 34 hard graph isomorphism benchmark families, encompassing 51,816 distinct graph instances. Notably, $\Delta$-DRESS distinguishes the Rook $L_2(4)$ vs. Shrikhande graph pair, which is theoretically indistinguishable by the 3-WL algorithm, showcasing its ability to surpass established limitations.
A simple vertex deletion fingerprint breaks graph isomorphism records, even distinguishing graphs that stump the classic 3-WL algorithm.
In this paper we study the single-deletion variant $\Delta$-DRESS, part of the broader DRESS framework. We demonstrate empirically that $\Delta$-DRESS, a single level of vertex deletion applied to the DRESS graph fingerprint, achieves unique fingerprints within each tested SRG parameter family across all 51,718 non-isomorphic strongly regular graphs (SRGs) considered, spanning 16 parameter families: the complete Spence collection (12 families, 43,703 graphs on up to 64 vertices) plus four additional SRG families with up to 4,466 graphs per family. Combined with 18 additional hard graph families (102 graphs including Miyazaki, Chang, Paley, Latin square, and Steiner constructions), $\Delta$-DRESS achieves 100% within-family separation across 34 benchmark families covering 51,816 distinct graph instances, implicitly resolving over 576 million within-family non-isomorphic pairs. Moreover, the classical Rook $L_2(4)$ vs. Shrikhande pair, SRG(16,6,2,2), is known to be indistinguishable by the original 3-WL algorithm, yet $\Delta$-DRESS separates it, proving that $\Delta$-DRESS escapes the theoretical boundaries of 3-WL. The method runs in polynomial time $\mathcal{O}(n \cdot I \cdot m \cdot d_{\max})$ per graph; a streamed implementation of the combined fingerprint uses $\mathcal{O}(m + B + n)$ memory, where $B$ is the number of histogram bins, while the experiments reported here additionally retain the full deleted-subgraph multiset matrix for post-hoc analysis.
