Questions tagged [graph-isomorphism]
The graph-isomorphism tag has no summary.
91 questions
0 votes
0 answers
44 views
What is a better than check all $N!$ permutations of vertices way of canonicalizing a DAG of up to 100 nodes and bounded degree of <= 16?
The labels on my DAGs are things like $A\times B$ but encoded in Unicode chars. Nauty is a no-go for me, and it doesn't work on multi-digraphs unless you encode them using a number on a single edge. ...
0 votes
0 answers
27 views
Making Graph Gluing (transformation)
I was studying graph gluing and came across the following example (All graphs are directed, for example, $e=(v_1,v_2)$ indicates that the corresponding edge starts from $v_1$ and goes to $v_2$): $I: V(...
0 votes
1 answer
132 views
Satisfiability to graph isomorphism reduction
$\text{GI} = \{\langle A, B \rangle∶ \text{ graph A is isomorphic to graph B} \}$ I want to reduce from, $\text{3SAT}\leq_p \text{GI}.$ I know how to reduce from GI to SAT: Whenever we see two ...
- 33
1 vote
1 answer
78 views
Relaxed form of the graph isomorphism problem?
Let $G_1=(L_1,R_1,E_1)$ and $G_2=(L_2,R_2,E_2)$ be bipartite directed graphs and let $\lambda:L_1\to L_2$ be a bijection between the $L$ vertex sets of the graphs. If I wanted to determine whether $...
- 257
2 votes
1 answer
122 views
Interactive proof for graphs with no non-trivial automorphisms
I am looking for an interactive proof for the language $AUTO^C= \{𝐺∣\text{𝐺 is an undirected graph that has no non-trivial automorphisms} \}$. I am interested in a method similar to the interactive ...
- 21
1 vote
1 answer
74 views
Reducing Subgraph Isomorphism problem to an instance of the Hamiltonian Cycle problem
How to reduce a Subgraph Isomorphism problem to an instance of the Hamiltonian Cycle problem (not the other way around)?
- 11
1 vote
0 answers
50 views
Efficiently generating the smallest directed graph subject to degree constraints that yields a requested flow
Given two (small-ish) sequences $I$ and $O$ of rational numbers with $\sum_{x \in I}x=\sum_{y \in O}y$, generate a directed graph $G = (V,E)$ with minimum $|V|$ that respects the following: $|I|$ ...
- 111
1 vote
1 answer
114 views
Weisfeiler-Leman Algorithm
We know that the Weisfeiler-Leman Algorithm will not always distinguish graphs that are not isomorphic but if two graphs are isomorphic are we guaranteed to get a certificate?
- 29
1 vote
1 answer
101 views
GNI public coin interactive proof: why randomize y?
I've read this scribe that provides a public coin interactive proof for graph non-isomorphism. In the proof, the verifier samples both a pairwise-independent hash function and a target $y$. Then it ...
- 13
2 votes
0 answers
90 views
How does the standard proof that IP is in PSPACE apply to, say, the graph non-isomorphism problem?
I learned years ago that $IP \subseteq PSPACE$ since you could simulate all sets of messages and then determine the probability of success. But lately I’ve been looking at the standard proof of this ...
- 53
1 vote
1 answer
99 views
Is graph isomorphism $P$-hard?
Intuitively speaking, it would seem like the graph isomorphism problem (which might be $NP$-intermediate) should be $P$-hard. But maybe it's not? Or maybe it's an open question? If it is indeed $P$-...
- 737
3 votes
1 answer
99 views
Largest isomorphic subgraphs of two graphs with features
the following question came up in a problem I am working on: Suppose you have two graphs $G_1=(V_1, E_1), G_2=(V_2,E_2)$ that have features attached to them, i.e. to every $v\in V_1$ or $v\in V_2$ ...
1 vote
2 answers
529 views
Automata: Are there algorithms to judge whether two automata are isomorphic?
When I want to judge whether two regular forms represent the same language, I have learned the next method: create the (non-deterministic) finite-state automata which accepts the language the given ...
- 9
0 votes
1 answer
640 views
Subgraph Isomorphism Problem NP complete?
I found many solution online on how to reduce Subgraph Isomorphism problem to Clique, but how do I prove that it is NP complete by reduction from independent set? I'm struggling to figure out this ...
1 vote
1 answer
78 views
Constructive Graph Isomorphism Algorithm Literature
I have consulted the literature concerning graph isomorphism algorithms, and all papers I could find involve finding a canonical representation of a graph. So to decide whether two graphs are ...
