ECCC-Report TR14-070https://eccc.weizmann.ac.il/report/2014/070Comments and Revisions published for TR14-070en-usFri, 16 May 2014 15:53:03 +0300
Paper TR14-070
| The Complexity of Geometric Graph Isomorphism |
Gaurav Rattan,
Vikraman Arvind
https://eccc.weizmann.ac.il/report/2014/070 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$.
Fri, 16 May 2014 15:53:03 +0300https://eccc.weizmann.ac.il/report/2014/070