# Tag Info

2

EDIT: changed a few things to make this work with the new constraint, also rewrote the whole proof to add details and clarity. The following is a reduction of minimum vertex cover to your problem. Take the graph $(V, E)$ we want to solve minimum vertex cover on. Set $|V_{1}| = |V|^{2} + |V| + |E|$, $|V_{2}| = |E| + |V|$. To every node $x \in V$ there ...

3

Under Karp reductions, the answer is exactly $\mathbf{NP}$: it is not hard to see that if a language is Karp-reducible to any $\mathbf{NP}$-language, then it is in $\mathbf{NP}$ too. On the other hand, all of $\mathbf{NP}$ reduces to $\mathbf{NP}$-complete languages by definition. Under Turing reductions, the answer is the class $\mathbf{P}^\mathbf{NP}$: ...

1

Your problem is equivalent to Graph Isomorphism under polynomial-time reductions, even if you include edge colors. First, GI is equivalent (under polynomial-time Turing reductions) to computing generators of the automorphism group. From those generators it is easy (using standard permutation group machinery) to compute the edge orbits in polynomial time. ...

4

It turns out that yes, indeed, there are two possible definitions for edge-automorphisms... but it turns out that they almost always coincide so that it seems that people often get away with not making the distinction. First, some notation. For a simple graph $G = (V,E)$ we let $\Gamma_V(G)$ define the group of automorpisms over the set of vertices $V$ ...

Top 50 recent answers are included