The Parameterized Complexity of Geometric Graph Isomorphism

We study the parameterized complexity of Geometric Graph Isomorphism (Known as the Point Set Congruence problem in computational geometry): given two sets of n points A and B with rational coordinates in k‐dimensional euclidean space, with k as the fixed parameter, the problem is to decide if there is a bijection $\mathit{\pi }:A\to B$ such that for all $x,y\in A$ , $\parallel x‐y\parallel =\parallel \mathit{\pi }(x)‐\mathit{\pi }(y)\parallel$ , where $\parallel ·\parallel$ is the euclidean norm. Our main result is the following: We give a $O^{\ast }(k^{O(k)})$ time (The $O^{\ast }(·)$ notation here, as usual, suppresses polynomial factors) FPT algorithm for Geometric Isomorphism. This is substantially faster than the previous best time bound of $O^{\ast }(2^{O(k^4)})$ for the problem (Evdokimov and Ponomarenko in Pure Appl Algebra 117–118:253–276, 1997). In fact, we show the stronger result that even canonical forms for finite point sets with rational coordinates can also be computed in $O^{\ast }(k^{O(k)})$ time. We also briefly discuss the isomorphism problem for other $l_p$ metrics. Specifically, we describe a deterministic polynomial‐time algorithm for finite point sets in ${‐{Q}}^2$ .