A graph G is isomorphic to a graph H if there is a relabeling of the vertices of G that produces H, and vice-versa. The graph-isomorphism problem (GI) is that of deciding whether graphs G and H are isomorphic.
5
votes
1answer
113 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 ...
4
votes
1answer
243 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 = ...
1
vote
0answers
66 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 ...
4
votes
2answers
146 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 ...
8
votes
1answer
184 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, ...
11
votes
1answer
197 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
vote
1answer
112 views
Is there any special property the resulting graph G' has?
Undirected graph $G$ can be partitioned into several vertex blocks, each vertex pair $(u,v)$ has an edge if "$u$" and "$v$" are in the different blocks; no edge, otherwise. That is, each block pair ...
11
votes
2answers
281 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 ...
11
votes
0answers
224 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). ...
11
votes
0answers
168 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? ...
9
votes
1answer
150 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 ...
3
votes
0answers
110 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 ...
8
votes
1answer
274 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 ...
14
votes
1answer
312 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 ...
-1
votes
2answers
177 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 ...
12
votes
1answer
355 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 ...
15
votes
1answer
685 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 ...
37
votes
0answers
1k 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, ...
5
votes
1answer
224 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 ...
14
votes
1answer
459 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 ...
5
votes
0answers
270 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 ...
4
votes
2answers
320 views
Questions on unification theory (and its application to DAG isomorphism )
While looking looking for an efficient and simple alg. for Directed Acyclic Graph isomorphism, i stumbled upon this which point out the similarity between DAG iso. and unification. After learning a ...
9
votes
3answers
557 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 ...
7
votes
1answer
772 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 ...
5
votes
2answers
445 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 ...
4
votes
3answers
508 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 ...
6
votes
0answers
218 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 ...
10
votes
1answer
361 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 ...
21
votes
3answers
1k 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 ...
14
votes
1answer
255 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 of BPP ...
3
votes
3answers
3k views
Polynomial Time Algorithm for Graph Isomorphism Testing [closed]
"Michael I. Troļ¬mov" 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 ...
15
votes
2answers
601 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)$ ...
11
votes
1answer
444 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?
10
votes
3answers
379 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 ...
