New answers tagged reductions
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
