# Tag Info

Accepted

Accepted

### Connections between Graph Isomorphism and Polynomial Equivalence

The paper you linked in the comments - and references therein - already seems to answer your first question. For your second question: I have little reason to think that there is a theorem of the ...
Accepted

Accepted

### Efficient graph isomorphism for similar graph queries

This is a simple polynomial time reduction to show that the problem is GI complete: even if you know that $G_1, G_2$ are isomorphic, checking if $G_3$, built from $G_2$ deleting and adding a node, is ...
Accepted

### A Combinatorial algorithm for trivalent graph isomorphism (except some small subclass)

Even higher-dimensional WL is known not to work in poly time on graphs of degree 4 (Cai-Furer-Immerman). I do not know if higher-dimensional WL might work on graphs of degree 3, but I also don't know ...
Accepted

### Complexity of a graph-rewriting problem

I don't know if it has been studied before, but after a quick look I think it should be PSPACE complete. We can build a reduction using the Nondeterministic Constraint Logic model of computation (NCL)...

### Complete problems or alternative definitions of the complexity class NP^GI?

[Summarizing the answers in the comments by Ricky Demer and Josh Grochow.] $\mathsf{NP}^{\mathsf{GI}} = \mathsf{NP}^{GraphIso}$, since these are nondeterministic poly-time Turing reductions, which ...

### Local Graph Isomorphism to construct Global Graph Isomorphism

This is actually how many graph isomorphism algorithms work (often in combination with Weisfeiler-Lehman). For example, bounded color class isomorphism (Luks 1983) works by first finding isomorphisms ...

### Complexity of testing if two sets of $m$ points in $\mathbb{R}^n$ differ only by rotation?

I think this is open. Note that if instead of testing equivalence under rotations you ask for equivalence under the general linear group, then already testing equivalence of degree three polynomials ...

### Complexity of graph isomorphism with properly colored edges (ref. request)

In general, if the number of adjacent edges, which have the same color, is bounded by a constant, say d. Then, the isomorphism problem for n-vertex graphs can be solved in n^(cd) for some constant c. ...