# Questions tagged [graph-isomorphism]

The tag has no usage guidance.

71 questions
Filter by
Sorted by
Tagged with
0answers
22 views

### Subgraph isomorphism index/precomputation

I'm currently working on problem in which a set of graphs $T=\{t_1,\dots,t_n\}$ is given and fixed. Given a graph $m$ I want to check which of the $t_i$ are subgraphs of it, as quick as possible. Is ...
1answer
228 views

### Rooted Tree Isomorphism Algorithm

I have developed an algorithm to determine if two rooted trees are isomorphic, which is based on the following conjecture: Let $S_{u}$ be the number of vertices in the rooted subtree of vertex $u$. ...
2answers
1k views

### How to define a similarity between two graphs?

Let's say we have a set of vertices $V$, and two (undirected) graphs over the same set $V$, but not necessarily the same set of edges $G_1 = (V, E_1)$, $G_2 = (V, E_2)$. $\newcommand\mG{\mathbb G}$(...
5answers
7k views

### Enumerate all non-isomorphic graphs of a certain size

I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class. In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ ...
2answers
399 views

### What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not. For example, consider the following two ...
1answer
380 views

### Why is Graph Isomorphism downward self reducible?

To say that graph isomorphism is downward self reducible means the following: There is an algorithm which decided graph isomorhpism for two given graphs of n vertices in polynomial time by accessing ...
0answers
50 views

2answers
3k views

### Graph isomorphism problem for labeled graphs

In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is ...
4answers
2k views

### Has the graph isomorphism problem been solved?

Wikipedia's graph isomorphism problem page would seem to indicate that, no, it has not been solved. However, a friend of mine pointed out A Polynomial Time Algorithm for Graph Isomorphism . I am not ...
1answer
81 views

### Is it a valid graph canonical form?

This question is motivated from this post. Let $G$ be a given graph, for each vertex $v \in V$, I will label $v$ with $Triangle(v)$. $Triangle(v) :$ means number of distinct triangles contain $v$. ...
1answer
60 views

### Proof that locality is sufficient in showing two graphs are isomorphic

Using the graph representation with (node, [list of neighbours]), to show that two graphs are isomorphic it is sufficient to: show that the vertices have the same degree and for every pair of ...
1answer
45 views

### Find isomorphism of graph with maximal number $x$ such that $f(x)\neq x$ - assuming $NP=P$

For $f : V → V$ which is authomorphism of directed graph $G = (V, E)$, $$\#f = |\{v : f(v) \neq v\}|$$ For graph $G$ we denote: $$\#G = \max\{\#f : \text{f is isomorphism G} \}$$ Prove ...
1answer
53 views

### Polynomial-time algorithm for Graph Isomorphism in case of Maximum Constrained Maximum Degree

From Wolfram: A polynomial time algorithm is however known for planar graphs (Hopcroft and Tarjan 1973, Hopcroft and Wong 1974) and when the maximum vertex degree is bounded by a constant (Luks ...
0answers
138 views

### Generating all directed multigraphs

I am trying to find an algorithm that generates all directed multigraphs with a given number of vertices and arcs up to isomorphism (no two generated graphs should be isomorphic). I also want to allow ...
1answer
64 views

### Algorithm for getting symetric vertex sets of undirected graph

For my application problem, I am searching for an algorithm that can find all symmetric vertex sets of an undirected labeled graph. My definition of symmetric vertex set is: Let $G$ be a graph with ...
0answers
119 views

### Generate all non-isomorphic bounded-degree rooted graphs of bounded radius

I need to generate/enumerate isomorphism classes of vertex-rooted graphs with the following properties. Let $\Delta$ be the maximal degree (say 3 for subcubic graphs) and $r$ the maximal distance of a ...
1answer
171 views

### Find Mapping Node in a Graph

Given two large directed graphs (may have loops and lonely nodes) A and B. They are structurally similar. If we give a node in Graph A, how to find the corresponding one in Graph B? Finally, we need ...
2answers
700 views

### Generating all directed acyclic graphs with constraints

I am interested in listing all the unlabeled1 acyclic digraphs with n vertices which satisfy some additional constraints, such as (a) the resulting graph is connected and (b) except for ...
1answer
143 views

### Literature about a naive approach to graph isomorphism by inspecting polynomials of adjacency matrices

I describe an approach to graph isomorphism which probably has false positives, and I am curious whether there is literature indicating that it does not work. Given two adjacency matrices $G, H$, an ...
0answers
96 views

### Shortest paths in isomorphic graphs with different edge weights

I'm looking for a way to find the shortest paths from a source to all destinations in isomorphic undirected graphs with different edge weights. The only thing I can think of is using Dijkstra on each ...
1answer
169 views

### Efficient algorithm for graph canonization for directed acyclic graphs?

I'm interesting in generating directed acyclic graphs (see here, for example). As part of this search, I'm curious if there are any efficient algorithms for determining a canonization of a directed ...
1answer
226 views

### Automorphism of a Graph with a given Set of Permutations

Given a graph $H$. A set of permutations $\alpha$ which contains permutations of vertices of $H$. The permutation set $\alpha$ has automorphisms of subgraph $H_1, H_2,..... H_x$ where $x$ is the ...
1answer
128 views

### If graph isomorphism yields a polynomial time algorihtm

Greeting I'm studying computing theory and are trying to grasp the concept of complexity classes. If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible ...
1answer
54 views

### On graph isomorphism over exponential word sizes

Is it known Graph isomorphism can be done in poly time if we allow exponential word sizes? (Shamir's poly time Integer Factoring algorithm is over exponential word sizes).
1answer
49 views

### Restricting possible permutations in Graph Isomorphism problem

Given a $2n$ vertex undirected graph whose vertices are partitioned arbitrarily in pairs to say WLOG $(1,2)$, $(3,4)$, $\dots$, $(2n-1,2n)$. Call these vertices pairs as super vertices. Call two such ...