TR14-070 Authors: Vikraman Arvind, Gaurav Rattan

Publication: 16th May 2014 15:53

Downloads: 2266

Keywords:

We study the complexity of Geometric Graph Isomorphism, in

$l_2$ and other $l_p$ metrics: given two sets of $n$ points $A,

B\subset \mathbb{Q}^k$ in

$k$-dimensional euclidean space the problem is to

decide if there is a bijection $\pi:A \rightarrow B$ such that for

all $x,y \in A$, $d(x,y) = d(\pi(x),\pi(y))$, where $d$ is the

distance given by the metric. Our results are the following:

1. We describe algorithms for isomorphism and canonization of point sets

with running time $k^{O(k)}\textrm{poly}(nM)$,

where $M$ upper bounds the binary encoding length of numbers in the

input. This is faster than previous algorithms for the problem.

2. From a complexity-theoretic perspective, we show that the

problem is in NP$[O(k^2 \log^2 k)]$ $\cap$ coIP$[O(k^2 \log^2 k)]$, where

$O(k^2 \log^2 k)$ respectively bounds the nondeterministic witness

length in NP and message length in the $2$-round IP protocol.

3. We also briefly discuss the isomorphism problem for other $l_p$ metrics.

We describe a deterministic logspace algorithm for point sets in $\mathbb{Q}^2$.