Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-070 | 14th May 2014 10:24

The Complexity of Geometric Graph Isomorphism


Authors: Vikraman Arvind, Gaurav Rattan
Publication: 16th May 2014 15:53
Downloads: 1449


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$.

ISSN 1433-8092 | Imprint