# Tag Info

Accepted

Accepted

### On a GI complete class

No, that's not $\mathrm{GI}$-complete unless $\mathrm{GI}\in\textsf{P}$. Indeed, isomorphism of such graphs can be checked in polynomial time. First, note that a bipartite graph is triangle-free. ...
• 4,485
Accepted

### Is the isomorphism problem between posets represented by DAGs GI-complete?

Graph isomorphism is GI-complete for DAGs: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI. The problem for partial orders is also GI-complete: We can reduce bipartite ...
• 1,831
Accepted

### Isomorphism of ‘ordered’ DAGs / acyclic semiautomata

If you only need to order the outgoing edges the problem is GI complete. Reduce from GI of directed graphs. Given a digraph $D$ make a new one $D’$ as follows: Make a vertex in $D’$ for every vertex ...
• 3,276
Accepted

### Can you find a counter-example for this proposed Graph Isomorphism algorithm?

Even without the hash function, this is basically just 1-dimensional Weisfeiler-Leman with individualization of a single vertex. Neuen & Schweitzer (STOC '18, arXiv) gave examples with an ...
• 37.7k
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 ...

• 4,485

### On lattice and code isomorphism

It's important to be precise about what it means to be a "minimum basis," which as Josh points out is not a priori well-defined. However, for lattice isomorphism the answer is basically that ...
• 5,013
Accepted

### One Generalization of Graph Isomorphism Problem

This is the decision version of what is sometimes called "Approximate Graph Isomorphism." While I won't say it's been studied a lot, it has been studied. See, for example: [AKKV] Arvind, Kobler, ...
• 37.7k
Accepted

### Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?

I think your focus on the rigid case of GI limits you too much. Instead phrase (non-rigid) GI as an HSP in the same way, but now the goal is to determine the size of the hidden subgroup, or a ...
• 37.7k