# Questions tagged [graph-isomorphism]

The tag has no usage guidance.

71 questions
Filter by
Sorted by
Tagged with
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 ...
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$. ...
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}$(...
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$ ...
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 ...
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 ...
50 views

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 ...
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 ...
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$. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...