All Questions
10 questions
0
votes
0
answers
69
views
What is the complexity of computing isomorphism of two non-regular graphs?
Regular graphs are the graphs in which the degree of each vertex is the same. Much research has gone into investigating isomorphism of regular graphs, and we know that computing isomorphism for ...
- 101
1
vote
0
answers
122
views
Hard instances for this graph isomorphism algorithm based on powers of weighted adjacency matrices?
In short, I found an algorithm for GI and the only hard instances
I found so far are non-isomorphic strongly regular graphs with
large automorphism groups.
Q1 What are hard instances for the ...
- 25.4k
2
votes
0
answers
54
views
Do there (or might there) exist computable invariants for Aut(G)-invariant subgraphs of a graph G?
I am interested in algorithms for computing all subgraphs (not necessarily induced) of a graph $G$ up to $Aut(G)$ isomorphism. I had the idea of partitioning the edges of the graph like so
$$\{F|E(G)\...
- 161
5
votes
2
answers
533
views
Diffie Hellman cryptography based on graph isomorphism?
We got a cryptographic algorithm and computer implementation
based on graph isomorphism.
An isomorphism between two graphs is a bijection between their vertices that pre
serves the edges.
For a graph $...
- 25.4k
1
vote
0
answers
177
views
Reduction graph isomorphism to maximum independent set in very dense graph
We got a reduction graph isomorphism to MIS in a very dense graph,
or alternatively negative monotone 2-CNF to MAX-ONEs with a formula
with many clauses.
Let $G,H$ be graphs of order $n$ and adjacency ...
- 25.4k
9
votes
3
answers
2k
views
Are regular graphs the hardest instance for graph isomorphism?
Regular graphs are the graphs in which the degree of each vertex is the same. The Weisfeiler-Lehman algorithm fails to distinguish between the given two non-isomorphic regular graphs.
Is there a ...
- 313
14
votes
1
answer
2k
views
Reasons for difficulty of Graph Isomorphism and why Johnson graphs are important?
In http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ it is mentioned:
'In discussing Johnson graphs, Babai said they were a source of “unspeakable ...
user76479
3
votes
3
answers
828
views
Algorithm to determine isomorphism of 2 maximal planar graphs
I read on wikipedia that there are efficient algorithms to answer the question whether 2 (maximal) planar graphs F and G are isomorphic. However, after some (IMHO) substantial searching I don't seem ...
3
votes
0
answers
540
views
Partitioning graph for Graph Isomorphism [closed]
Motivation: I am studying the graph isomorphism problem. I am trying to construct a partitioning method to reduce search cases .
Construction:
$G$ is an $r$ regular graph, $k$ connected (not a ...
- 267
8
votes
2
answers
355
views
Isomorphism problem on the class of induced subgraphs of a hypercube
A problem that I am currently studying translates to the problem of deciding whether two induced subgraphs of the hypercube $Q_k$ are isomorphic.
Now it feels to me that this class of graphs is "too ...
- 3,463