Questions tagged [graph-isomorphism]
Two graphs G, H are isomorphic if there is a relabeling of the vertices of G that produces H, and vice-versa. The graph isomorphism problem (GI) is to decide whether two given are isomorphic. In addition to its practical interest, it was identified by Karp in 1972 as having unknown complexity, is one of the few remaining natural candidates for an NP-intermediate problem, and led to the creation of the complexity class AM.
137
questions
16
votes
1
answer
516
views
Counterexample for Corneil's efficient algorithm for Graph Isomorphism
In the paper An Efficient Algorithm for Graph Isomorphism by Corneil and Gotlieb, 1970 a conjecture was stated upon which the stated algorithm relied for solving GI in polynomial time. Namely:
that ...
- 568
10
votes
1
answer
500
views
Is graph isomorphism in UP ${\cap}$ coUP?
Is graph isomorphism (the decision problem) in $\mathsf{UP}\cap \mathsf{coUP}$? Here $\mathsf{UP}$ is the class of decision problems accepted by an unambiguous Turing machine (see the complexity zoo).
11
votes
3
answers
761
views
History and status of the graph matching problem
Part of the difficulty of finding out more about this problem is that the graph matching problem is different from its much more famous cousin, the matching problem, but hard to be distinguished from ...
- 1,165
6
votes
1
answer
309
views
Canonical labeling of special classes of DAGs
Graph Isomorphism of directed acyclic graphs (DAGs) is known to be GI-complete. So a polynomial time algorithm to canonize DAGs is not known.
What are some special classes of DAGs that can be ...
- 10.6k
4
votes
1
answer
289
views
How hard is to compute $\Delta_{|V|}$?
Let $G=(V,E)$ be a graph. Let $\Delta_k$ be the quantity defined in this question. Let $\mathcal{C}$ be the set of vertex covers of $G$. The following holds:
$$
|\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^...
- 6,842
1
vote
0
answers
103
views
Equivalence relations on strongly regular graphs with same parameters
Let $\mathcal{S}$ be the set of all strongly regular graphs with parameter
$(n, k, \lambda, \mu)$. Are there any (interesting) equivalence relations defined on this set?
My motivation is to approach ...
- 1,281
4
votes
2
answers
604
views
Optimal upper bound on the number of non-isomorphic graphs with certain parameter
What are the optimal (or best known) bounds (preferably exact or else asymptotic but not expectation on random graphs) on the number of non-isomorphic (unlabelled) simple (no self-loop), undirected ...
- 1,281
12
votes
1
answer
748
views
automorphism in Cai-Furer-Immerman gadgets
In the famous counter example for graph isomorphism via Weisfeiler-Lehman (WL) method the following gadget was constructed in this paper by Cai, Furer and Immerman.
They construct a graph $X_k = (V_k, ...
- 1,281
12
votes
1
answer
338
views
Negative results on identical particles approach to Graph Isomorphism (GI) problem
There has been some efforts to attack graph isomorphism problem using quantum random walk of hard-core bosons (symmetric but no double occupancy). Symmetric power of adjacency matrix, which seemed ...
- 1,281
14
votes
2
answers
529
views
Approaches to GI inspired by knot problem
GI and Knot Problem both are problem of deciding structural equivalence of mathematical objects. Are there any results establishing connections between them? Nice connections of knot problem to ...
- 1,281
11
votes
1
answer
399
views
Redundancy and Structure of computational problems
It is widely believed that some computational problems such as graph isomorphism can not be NP-complete because it does not possess enough structure or redundancy to be computationally hard (NP-hard). ...
- 20.9k
16
votes
1
answer
448
views
Strongly Regular Graph and GI-Completeness
It is not known if graph isomorphism (GI) for strongly regular graphs (SRGs) is in P. Are there any hints that it might or might not be GI-Complete? Are there any strong consequences in such cases? (...
- 1,281
17
votes
2
answers
437
views
similar matrices
Given two $n \times n$ matrices $A$ and $B$, the problem of deciding if there exist a permutation matrix $P$ such that $B = P^{-1}AP$ is equivalent to GI(Graph ...
- 1,281
6
votes
2
answers
411
views
Complexity of algorithm to test if a graph is asymmetric
Counting the order of automorphism group of a graph is polynomial-time equivalent to graph isomorphism problem. But if we just want to know if the order is greater than 1, what is the complexity of ...
- 1,281
17
votes
2
answers
2k
views
Gentle introduction to graph isomorphism for bounded valance graphs
I am reading about classes of graphs for which Graph Isomorphism ($GI$) is in $P$. One of such case is graphs of bounded valence (maximum over degree of each vertex) as explained here. But I found it ...
- 1,281
15
votes
1
answer
496
views
Imperfect subgraph isomorphism
Consider the following problem: Given a query graph $G = (V, E)$ and a reference graph $G' = (V', E')$, we want to find the injective mapping $f : V \rightarrow V'$ which minimizes the number of edges ...
- 9,269
0
votes
2
answers
269
views
Complexity of finding if a degree bounded graph H is a subgraph of an unbounded graph G
You are given two graphs G and H , and want to know if H is a subgraph of G.
You know that H has a max vertex degree K (constant integer).
What can you say about the complexity of this?
I know that ...
- 143
15
votes
1
answer
815
views
Hardness of Computing Weisfeiler-Lehman labels
The 1-dim Weisfeiler-Lehman algorithm (WL) is commonly known as canonical labeling or color refinement algorithm. It works as follows :
The initial coloring $C_0$ is uniform, $C_0(v) = 1$ for all ...
- 10.6k
16
votes
1
answer
1k
views
NP-hardness of a graph partition problem?
I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic?
Here $E$ is ...
- 20.9k
54
votes
1
answer
2k
views
Is there a gap amplification type of result for the Graph Isomorphism Problem?
Suppose $G_1$ and $G_2$ are two undirected graphs on vertex set $\{1, \dotsc, n\}$. The graphs are isomorphic if and only if there is a permutation $\Pi$ such that $G_1 = \Pi(G_2)$, or more formally, ...
- 619
6
votes
1
answer
339
views
Best lower bound for proof complexity of graph non-automorphism problem
Graph automorphism problem ( GA) of determining whether a graph has a nontrivial automorphism is a good candidate for a problem in NP-intermediate. I'm looking for references that study the ...
- 20.9k
22
votes
1
answer
1k
views
What is the current known hardness of Graph Isomorphism?
Inspired by the question is factoring known to be P-hard, I wonder what the current similar state of knowledge is about the hardness of graph isomorphism. I am sure that it is currently not known if ...
- 905
9
votes
2
answers
432
views
Efficient algorithms for searching a collection of trees
I have a large dataset of trees and I would like to search it by specifying a treelet (connected subgraph). The query should return all the occourrences of the treelet in the dataset.
Are there ...
6
votes
2
answers
1k
views
Questions on unification theory (and its application to DAG isomorphism )
While looking looking for an efficient and simple algorithm for directed acyclic graph isomorphism, I stumbled upon this which points out the similarity between DAG isomorphism and unification. After ...
- 161
11
votes
3
answers
1k
views
Regular Graphs and Isomorphism
I would like to ask whether there is an already published result on that:
We take all possible different paths between each pair of nodes of two connected regular (with degree $d$ let's say, and ...
- 573
16
votes
2
answers
3k
views
Hard Instances for graph isomorphism testing
Is the case of strongly regular graphs
the hardest one for GI testing?
where "hardest" is used in some "common sense" meaning, or "in average", so to speak.
Wolfram MathWorld mentions some "...
- 479
5
votes
2
answers
780
views
Number of non-isomorphic connected graphs of $n$ nodes and $m$ edges
Let $G( n, m )$ be the set of all possible connected graphs of $n$ nodes and $m$ edges such that, for each $g_1 \in G( n, m )$, $g_2 \in G( n, m )$, if $g_1 \neq g_2$ then $g_1$ and $g_2$ are non-...
- 6,842
5
votes
3
answers
756
views
Is this graph transformation unique up to isomorphism? [Answer:NO]
Suppose, transformation T is defined as given in the diagrams below.
Every vertex (v) is replaced by ...
- 1,924
7
votes
0
answers
393
views
Embedded dynamic programming (and planar subgraph isomorphism)
In Planar Subgraph Isomorphism Revisited, Frederic Dorn obtains an improved algorithm for Planar Subgraph Isomorphism, by using a technique he calls Embedded Dynamic Programming. This technique ...
- 6,994
10
votes
1
answer
551
views
Is there a polynomial-time algorithm to solve graph isomorphism for Delaunay graphs of (finite) hexagonal tessellations?
Given a finite plane, I have a hexagonal tessellation of that plane with a fixed-size regular hexagon. I then compute the Delaunay graph G for the tessellation. Given such a graph G, I delete specific ...
- 655
31
votes
3
answers
4k
views
coNP certificate for Graph Isomorphism
It is easy to see that graph isomorphism(GI) is in NP. It is a major open problem whether GI is in coNP. Are there any potential candidates of properties of graphs that can be used as coNP ...
- 10.6k
14
votes
1
answer
355
views
Generating Graphs with Trivial Automorphisms
I'm revising some cryptographic model. To show its inadequacy, I've devised a contrived protocol based on graph isomorphism.
It is "commonplace" (yet controversial!) to assume the existence ...
- 16.5k
7
votes
3
answers
5k
views
Polynomial Time Algorithm for Graph Isomorphism Testing [closed]
"Michael I. Trofimov" claims that he has found a poly-time algorithm for graph isomorphism, which works for all graphs.
The paper is given in arXiv. The companion website gives a proof-of-concept ...
- 16.5k
23
votes
2
answers
1k
views
Relationship between symmetry and computational intractability?
The $k$-fixed point free automorphism problem asks for a graph automorphism which moves at least $k(n)$ nodes. The problem is $NP$-complete if $k(n)=n^c$ for any $c$>0.
However, If $k(n)=O(\log n)$...
- 20.9k
11
votes
1
answer
587
views
what are known bounds on complexity of nontrivial graph automorphism
Given any simple undirected graph G, it is nontrivial to determine if G has nontrivial (non-identity) automorphisms. But what are results on upper/lower bounds of this decision problem?
- 131
12
votes
3
answers
752
views
$NP\cap coAM$ Languages
What other problems languages different than graph isomorphism are in $NP\cap coAM$? Can you give some references?
Update: I forgot to mention that I'm interested in languages not known to be in $...
- 3,290
25
votes
3
answers
1k
views
Graph Isomorphism and hidden subgroups
I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?
- 32.1k